시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB50252450.000%

문제

A couple of years ago the Bergen Ministry of Infrastructure prepared a plan for a new light railway network. This network was supposed to connect all n neighbourhoods in the city with n−1 railway tracks in such a way, that there would be a path from every neighbourhood to every other neighbourhood. The planned tracks are identified by numbers from 1 to n − 1.

Years passed, new elections are approaching, and the railway network still exists only on paper. Therefore the Minister of Infrastructure (representing a party holding disagreement in high regard) decided to construct at least some part of the plan. He asked each of his m deputy ministers to choose which neighbourhoods they thought should be connected. That will result in a list of necessary tracks for each deputy minister. If a deputy minister thinks that the neighbourhoods a1, . . . , as need to be connected, then according to him or her, the necessary tracks are all those which lie on planned paths from ai to aj for some 1 ≤ i < j ≤ s.

The minister just received all lists from the deputy ministers. He decided to construct in the first place the tracks which are requested by at least k deputy ministers. Your task is to prepare a list of these tracks.

입력

In the first line of the input there are three integers n, m and k. The next n − 1 lines contain the plan; in the i-th of these lines there are two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), specifying that the i-th track on the plan is between neighbourhoods ai and bi.

In the next m lines there are neighbourhoods chosen by deputy ministers; the i-th of these lines begins with an integer si which specify the number of neighbourhoods chosen by the i-th deputy minister. After it there are si integers specifying these neighbourhoods. The total length of all lists of deputy ministers is at most S, i.e. ∑si ≤ S.

출력

In the first line of the output you should write one integer r, specifying the number of tracks which are requested by at least k deputy ministers. In the second line you should write r identifiers of these tracks in ascending order.

제한

We always have 2 ≤ si ≤ n ≤ 100 000, S ≤ 100 000, and 1 ≤ k ≤ m ≤ 50 000. For subcases, the inputs have these further restrictions.

서브태스크

번호배점제한
18

n ≤ 10 000, S ≤ 2 000

215

n ≤ 10 000, m ≤ 2 000

37

Every neighbourhood is the endpoint of at most 2 planned tracks.

429

k = m, si = 2

516

k = m

625

No further restrictions.

예제 입력 1

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

예제 출력 1

2
2 3

힌트

The first deputy minister thinks that tracks 1–3, 2–3, 3–4 and 4–5 are necessary. The second deputy minister considers tracks 3–4 and 4–6, and the third one only track 2–3. Tracks 2–3 and 3–4 are necessary according to at least two deputy ministers.

채점 및 기타 정보

  • 예제는 채점하지 않는다.