Baltic OI '17 P3 - Railway - DMOJ: Modern Online Judge

Baltic OI '17 P3 - Railway

View as PDF

Submit solution

All submissions

Best submissions

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 $n$ $n$ neighbourhoods in the city with $n-1$ $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$ $1$ to $n-1$ $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$ $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 $a_1, \dots, a_s$ $a_{1}, \dots, a_{s}$ need to be connected, then according to him or her, the necessary tracks are all those which lie on planned paths from $a_i$ $a_{i}$ to $a_j$ $a_{j}$ for some $1 \le i < j \le s$ $1 \leq i < j \leq 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$ $k$ deputy ministers.

Your task is to prepare a list of these tracks.

Input Specification

In the first line of the input there are three integers $n$ $n$ , $m$ $m$ and $k$ $k$ . The next $n-1$ $n - 1$ lines contain the plan; in the $i$ $i$ -th of these lines there are two integers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ ( $1 \le a_i, b_i \le n$ $1 \leq a_{i}, b_{i} \leq n$ , $a_i \ne b_i$ $a_{i} \neq b_{i}$ ), specifying that the $i$ $i$ -th track on the plan is between neighbourhoods $a_i$ $a_{i}$ and $b_i$ $b_{i}$ .

In the next $m$ $m$ lines there are neighbourhoods chosen by deputy ministers; the $i$ $i$ -th of these lines begins with an integer $s_i$ $s_{i}$ which specify the number of neighbourhoods chosen by the $i$ $i$ -th deputy minister. After it there are $s_i$ $s_{i}$ integers specifying these neighbourhoods. The total length of all lists of deputy ministers is at most $S$ $S$ , i.e. $\sum_{i=1}^m s_i \le S$ $\sum_{i = 1}^{m} s_{i} \leq S$ .

Constraints

We always have $2 \le s_i \le n \le 100\,000$ $2 \leq s_{i} \leq n \leq 100 000$ , $S \le 100\,000$ $S \leq 100 000$ , and $1 \le k \le m \le 50\,000$ $1 \leq k \leq m \leq 50 000$ . For subcases, the inputs have these further restrictions:

Group 1: 8 points $n \le 10\,000$ $n \leq 10 000$ , $S \le 2\,000$ $S \leq 2 000$ ,
Group 2: 15 points $n \le 10\,000$ $n \leq 10 000$ , $m \le 2\,000$ $m \leq 2 000$ ,
Group 3: 7 points Every neighbourhood is the endpoint of at most 2 planned tracks.
Group 4: 29 points $k=m$ $k = m$ , $s_i= 2$ $s_{i} = 2$ ,
Group 5: 16 points $k=m$ $k = m$ ,
Group 6: 25 points No further restrictions.

Output Specification

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

Sample Input

Copy

Sample Output

Copy

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.

Comments

There are no comments at the moment.