P6572 [BalticOI 2017] Railway

One year ago, the Bergen Ministry of Infrastructure planned to connect all cities with roads. Unfortunately, after a year, the project was abandoned. So the minister decided to restart the plan and make it a bit simpler.

The original plan was to connect $n$ cities with $n-1$ roads. Now there are $m$ vice ministers, and each vice minister believes that some cities must be connected. For example, if a vice minister wants to connect $a$ and $c$, and there are two roads $a - b$ and $b - c$, then this vice minister’s requirement is equivalent to selecting these two roads. Now you need to find which roads are selected by at least $k$ vice ministers. The minister came to you and asked you to find these roads.

The first line contains three integers $n, m, k$, representing the number of cities, the number of vice ministers, and the minimum number of vice ministers that must select a road. The next $n-1$ lines each contain two integers $a_i$ and $b_i$, meaning that the $i$-th road is between $a_i$ and $b_i$. The roads are numbered from $1$ to $n-1$. The next $m$ lines start with an integer $s_i$, meaning that this vice minister thinks there are $s_i$ cities that need to be connected, followed by $s_i$ integers indicating which cities they are.

The first line contains an integer $r$, the number of roads that are selected by at least $k$ vice ministers. The second line contains $r$ integers, the indices of these roads in increasing order.

#### Sample Explanation The requirements of $3$ vice ministers are as follows: - $1-3, 2-3, 3-4, 4-5$ - $3-4, 4-6$ - $2-3$ The roads selected by at least $2$ vice ministers are road $2$ and road $3$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (8 pts): $n \le 10^4$, $\sum s_i \le 2 \times 10^3$. - Subtask 2 (15 pts): $n \le 10^4$, $m \le 2 \times 10^3$. - Subtask 3 (7 pts): Each city is an endpoint of at most $2$ roads. - Subtask 4 (29 pts): $k = m$, $s_i = 2$. - Subtask 5 (16 pts): $k = m$. - Subtask 6 (25 pts): No special constraints. For $100\%$ of the testdata, $2 \le s_i \le n \le 10^5$, $1 \le k \le m \le 5 \times 10^4$, $\sum s_i \le 10^5$. #### Note **Translated from [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T2 Railway.** Translator: @[一只书虫仔](https://www.luogu.com.cn/user/114914)。 Translated by ChatGPT 5