Background

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.

Problem Description

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.

Input Format

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.

Output Format

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.

6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2

2
2 3

Hint

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 T2 Railway.
Translator: @一只书虫仔。

Translated by ChatGPT 5