CF786E.ALT

ALT is a planet in a galaxy called "Encore". Humans rule this planet but for some reason there's no dog in their planet, so the people there are sad and depressed. Rick and Morty are universal philanthropists and they want to make people in ALT happy.

ALT has n cities numbered from 1 to n and n - 1 bidirectional roads numbered from 1 to n - 1. One can go from any city to any other city using these roads.

There are two types of people in ALT:

1. Guardians. A guardian lives in a house alongside a road and guards the road.
2. Citizens. A citizen lives in a house inside a city and works in an office in another city.

Every person on ALT is either a guardian or a citizen and there's exactly one guardian alongside each road.

Rick and Morty talked to all the people in ALT, and here's what they got:

• There are m citizens living in ALT.
• Citizen number i lives in city number x__i and works in city number y__i.
• Every day each citizen will go through all roads along the shortest path from his home to his work.
• A citizen will be happy if and only if either he himself has a puppy himself or all of guardians along his path to his work has a puppy (he sees the guardian's puppy in each road and will be happy).
• A guardian is always happy.

You need to tell Rick and Morty the minimum number of puppies they need in order to make all people in ALT happy, and also provide an optimal way to distribute these puppies.

ALT 是银河系“Encore”中的一颗行星。人类统治着这颗行星，但不知何故，这颗行星上没有狗，因此当地居民感到悲伤和沮丧。瑞克和莫蒂是宇宙级的慈善家，他们希望让 ALT 上的居民快乐起来。

ALT 上有 $n$ 座城市，编号为 $1$ 到 $n$，以及 $n-1$ 条双向道路，编号为 $1$ 到 $n-1$。任意两座城市之间均可通过这些道路相互到达。

ALT 上有两种人：

1. 守护者（Guardian）：守护者住在某条道路旁的房子里，负责看守该道路。
2. 市民（Citizen）：市民住在某座城市的房子里，并在另一座城市的办公室工作。

ALT 上的每个人要么是守护者，要么是市民，且每条道路上恰好有一位守护者。

瑞克和莫蒂与 ALT 上的所有人进行了交谈，得到了以下信息：

• ALT 上共有 $m$ 位市民；
• 第 $i$ 位市民住在城市 $x_i$，并在城市 $y_i$ 工作；
• 每天，每位市民都会沿着从其住所到工作地的最短路径经过所有道路；
• 当且仅当以下任一条件成立时，该市民才会开心：
  • 他本人拥有一只小狗；或
  • 他通勤路径上所有守护者都拥有一只小狗（他在每条路上都能看到守护者的小狗，从而感到开心）；
• 所有守护者始终是开心的。

你需要告诉瑞克和莫蒂：为了让 ALT 上的所有人都开心，所需的最少小狗数量是多少？并给出一种最优的小狗分配方案。

The first line of input contains two integers n and m (2 ≤ n ≤ 2 × 104, 1 ≤ m ≤ 104) — number of cities and number of citizens respectively.

The next n - 1 lines contain the roads, i-th line contains endpoint of i-th edge, v and u (1 ≤ v, u ≤ n, v ≠ u).

The next m lines contain the information about citizens. i-th line contains two integers x__i and y__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i).

输入的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \times 10^4$，$1 \leq m \leq 10^4$）—— 分别表示城市的数量和市民的数量。

接下来的 $n - 1$ 行描述道路，其中第 $i$ 行包含第 $i$ 条边的两个端点 $v$ 和 $u$（$1 \leq v, u \leq n$，$v \neq u$）。

接下来的 $m$ 行描述市民的信息。其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$，$x_i \neq y_i$）。

In the first line of input print a single integer k, the total number of puppies they need (1 ≤ k ≤ n).

In the second line print an integer q, the number of puppies to give to citizens, followed by q distinct integers _a_1, _a_2, ..., a__q, index of citizens to give puppy to (0 ≤ q ≤ min(m, k), 1 ≤ a__i ≤ m).

In the third line print an integer e, the number of puppies to give to guardians, followed by e distinct integers _b_1, _b_2, ..., b__e, index of road of guardians to give puppy to (0 ≤ e ≤ min(n - 1, k), 1 ≤ b__i ≤ n - 1).

Sum of q and e should be equal to k.

在输入的第一行输出一个整数 $k$，表示他们总共需要的小狗数量（$1 \leq k \leq n$）。

在第二行输出一个整数 $q$，表示要分发给市民的小狗数量，随后输出 $q$ 个互不相同的整数 $a_1,\ a_2,\ \dots,\ a_q$，表示将小狗分发给的市民编号（$0 \leq q \leq \min(m,\ k)$，$1 \leq a_i \leq m$）。

在第三行输出一个整数 $e$，表示要分发给守卫者的小狗数量，随后输出 $e$ 个互不相同的整数 $b_1,\ b_2,\ \dots,\ b_e$，表示将小狗分发给的守卫者所负责的道路编号（$0 \leq e \leq \min(n-1,\ k)$，$1 \leq b_i \leq n-1$）。

$q$ 与 $e$ 的和应等于 $k$。

Map of ALT in the first sample testcase (numbers written on a road is its index):

Map of ALT in the second sample testcase (numbers written on a road is its index):

第一个样例测试用例中 ALT 的地图（道路上标注的数字为其索引）：

第二个样例测试用例中 ALT 的地图（道路上标注的数字为其索引）：