## Baltic OI '17 P3 - Railway

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem types
##### Baltic Olympiad in Informatics: 2017 Day 1, Problem 3

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 neighbourhoods in the city with 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 to .

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 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 need to be connected, then according to him or her, the necessary tracks are all those which lie on planned paths from to for some . 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 deputy ministers.

#### Input Specification

In the first line of the input there are three integers , and . The next lines contain the plan; in the -th of these lines there are two integers and (, ), specifying that the -th track on the plan is between neighbourhoods and .

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

#### Constraints

We always have , , and . For subcases, the inputs have these further restrictions:

• Group 1: 8 points , ,
• Group 2: 15 points , ,
• Group 3: 7 points Every neighbourhood is the endpoint of at most 2 planned tracks.
• Group 4: 29 points , ,
• Group 5: 16 points ,
• Group 6: 25 points No further restrictions.

#### Output Specification

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

#### Sample Input

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

#### Sample Output

2
2 3

#### Explanation of Sample Output

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.