{"raw_statement":[{"iden":"statement","content":"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.\n\nALT 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.\n\nThere are two types of people in ALT:\n\n1. Guardians. A guardian lives in a house alongside a road and guards the road.\n2. Citizens. A citizen lives in a house inside a city and works in an office in another city.\n\nEvery person on ALT is either a guardian or a citizen and there's exactly one guardian alongside each road.\n\nRick and Morty talked to all the people in ALT, and here's what they got:\n\n* There are _m_ citizens living in ALT.\n* Citizen number _i_ lives in city number _x__i_ and works in city number _y__i_.\n* Every day each citizen will go through all roads along the shortest path from his home to his work.\n* 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).\n* A guardian is always happy.\n\nYou 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."},{"iden":"input","content":"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.\n\nThe 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_).\n\nThe 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_)."},{"iden":"output","content":"In the first line of input print a single integer _k_, the total number of puppies they need (1 ≤ _k_ ≤ _n_).\n\nIn 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_).\n\nIn 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).\n\nSum of _q_ and _e_ should be equal to _k_."},{"iden":"examples","content":"Input\n\n4 5\n2 4\n3 4\n1 4\n2 4\n2 1\n2 4\n1 2\n2 3\n\nOutput\n\n3\n1 5 \n2 3 1 \n\nInput\n\n4 7\n3 4\n1 4\n2 1\n4 2\n4 2\n2 4\n1 4\n2 1\n3 1\n4 2\n\nOutput\n\n3\n1 6 \n2 2 3"},{"iden":"note","content":"Map of ALT in the first sample testcase (numbers written on a road is its index):\n\nMap of ALT in the second sample testcase (numbers written on a road is its index):\n\n"}],"translated_statement":[{"iden":"statement","content":"ALT 是一个名为 \"Encore\" 的星系中的行星。人类统治着这颗行星，但出于某种原因，这颗星球上没有狗，因此那里的居民感到悲伤和沮丧。里克和莫蒂是普世的慈善家，他们希望让 ALT 的所有人变得快乐。\n\nALT 有 #cf_span[n] 座城市，编号从 #cf_span[1] 到 #cf_span[n]，以及 #cf_span[n - 1] 条双向道路，编号从 #cf_span[1] 到 #cf_span[n - 1]。通过这些道路，可以从任意一座城市到达任意其他城市。\n\nALT 上有两种人：\n\nALT 上的每个人要么是守护者，要么是市民，且每条道路旁恰好有一位守护者。\n\n里克和莫蒂与 ALT 上的所有人交谈后，得到了以下信息：\n\n你需要告诉里克和莫蒂，为了让 ALT 的所有人快乐，他们至少需要多少只小狗，并提供一种最优的小狗分配方案。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2 × 104]，#cf_span[1 ≤ m ≤ 104]）——分别表示城市数量和市民数量。\n\n接下来的 #cf_span[n - 1] 行描述道路，第 #cf_span[i] 行包含第 #cf_span[i] 条边的两个端点 #cf_span[v] 和 #cf_span[u]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]）。\n\n接下来的 #cf_span[m] 行描述市民信息，第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ n]，#cf_span[xi ≠ yi]）。\n\n第一行输出一个整数 #cf_span[k]，表示他们需要的小狗总数（#cf_span[1 ≤ k ≤ n]）。\n\n第二行输出一个整数 #cf_span[q]，表示分给市民的小狗数量，后跟 #cf_span[q] 个互不相同的整数 #cf_span[a1, a2, ..., aq]，表示获得小狗的市民编号（#cf_span[0 ≤ q ≤ min(m, k)]，#cf_span[1 ≤ ai ≤ m]）。\n\n第三行输出一个整数 #cf_span[e]，表示分给守护者的小狗数量，后跟 #cf_span[e] 个互不相同的整数 #cf_span[b1, b2, ..., be]，表示获得小狗的道路编号（守护者所在道路）（#cf_span[0 ≤ e ≤ min(n - 1, k)]，#cf_span[1 ≤ bi ≤ n - 1]）。\n\n#cf_span[q] 和 #cf_span[e] 的和应等于 #cf_span[k]。\n\n第一个测试用例中 ALT 的地图（道路上的数字为其编号）：\n\n第二个测试用例中 ALT 的地图（道路上的数字为其编号）：\n\n"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n ≤ 2 × 104]，#cf_span[1 ≤ m ≤ 104]）——分别表示城市数量和市民数量。接下来的 #cf_span[n - 1] 行描述道路，第 #cf_span[i] 行包含第 #cf_span[i] 条边的两个端点 #cf_span[v] 和 #cf_span[u]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]）。接下来的 #cf_span[m] 行描述市民信息，第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi, yi ≤ n]，#cf_span[xi ≠ yi]）。"},{"iden":"output","content":"第一行输出一个整数 #cf_span[k]，表示他们需要的小狗总数（#cf_span[1 ≤ k ≤ n]）。第二行输出一个整数 #cf_span[q]，表示分给市民的小狗数量，后跟 #cf_span[q] 个互不相同的整数 #cf_span[a1, a2, ..., aq]，表示获得小狗的市民编号（#cf_span[0 ≤ q ≤ min(m, k)]，#cf_span[1 ≤ ai ≤ m]）。第三行输出一个整数 #cf_span[e]，表示分给守护者的小狗数量，后跟 #cf_span[e] 个互不相同的整数 #cf_span[b1, b2, ..., be]，表示获得小狗的道路编号（守护者所在道路）（#cf_span[0 ≤ e ≤ min(n - 1, k)]，#cf_span[1 ≤ bi ≤ n - 1]）。#cf_span[q] 和 #cf_span[e] 的和应等于 #cf_span[k]。"},{"iden":"examples","content":"输入\n4 5\n2 4\n3 4\n1 4\n2 4\n2 1\n2 4\n1 2\n2 3\n输出\n3\n1 5\n2 3 1\n\n输入\n4 7\n3 4\n1 4\n2 1\n4 2\n4 2\n2 4\n1 4\n2 1\n3 1\n4 2\n输出\n3\n1 6\n2 2 3 "},{"iden":"note","content":"第一个测试用例中 ALT 的地图（道路上的数字为其编号）：\n\n第二个测试用例中 ALT 的地图（道路上的数字为其编号）：\n\n"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of cities, $ m \\in \\mathbb{Z} $ the number of citizens. \nLet $ G = (V, E) $ be a tree with $ V = \\{1, \\dots, n\\} $ and $ E = \\{e_1, \\dots, e_{n-1}\\} $, where each edge $ e_i $ connects two distinct cities and is associated with a guardian. \nLet $ C = \\{(x_1, y_1), \\dots, (x_m, y_m)\\} $ be a set of $ m $ citizen requests, where each $ (x_i, y_i) $ denotes a pair of cities that citizen $ i $ wishes to connect via a path containing at least one puppy.\n\n**Constraints** \n1. $ 2 \\leq n \\leq 2 \\times 10^4 $ \n2. $ 1 \\leq m \\leq 10^4 $ \n3. Each $ e_i \\in E $ has a unique guardian. \n4. Each citizen $ i \\in \\{1, \\dots, m\\} $ requires that at least one edge on the unique path between $ x_i $ and $ y_i $ in $ G $ receives a puppy.\n\n**Objective** \nFind the minimum number $ k $ of puppies and a distribution: \n- A subset $ Q \\subseteq \\{1, \\dots, m\\} $ of citizens to whom puppies are directly given (size $ q = |Q| $), \n- A subset $ E' \\subseteq \\{1, \\dots, n-1\\} $ of edges (guardians) to whom puppies are given (size $ e = |E'| $), \nsuch that $ q + e = k $, and every citizen request $ (x_i, y_i) $ is satisfied — i.e., either citizen $ i \\in Q $, or at least one edge on the path from $ x_i $ to $ y_i $ is in $ E' $. \n\nMinimize $ k $.","simple_statement":null,"has_page_source":false}