sol

The Byzantine Empire is again being attacked by the Turks. In order to ask for help, the emissaries of the Byzantine emperor have to reach the capitals of N neighboring kingdoms. Between these cities there are M two-way roads, built so that from any city one may get to any other city, directly or indirectly, by passing through other cities. However, the roads are unsafe because there are K thieves' guilds that control them. Each road is controlled by a single guild and in order to be traveled upon you have to pay a passage fee (which is the same for all roads). A thieves’ guild can control more than one road, but only allows passage on one of them. Also, the emissaries don't want to pay the passage fee for more roads than it's necessary. On a road for which the passage fee has been paid you can go as many times as you want in any direction.
The emissaries always start in city 1.

Task

Write a program that calculates a minimum number of roads for which the passage fee has to be paid so that any city be accessible from city 1 by traveling only on these roads, and no thieves’ guild controls more than one of the roads selected.

Input Data

Input file sol.in has the following structure:
- line one contains three positive integers separated by a single space, N M K, representing the number of cities, number of roads and number of thieves' guilds;
- lines 2, . . . , M+1 contain two positive integers separated by a space, x y (1<=x,y<=N), with the meaning that between city x and city y there is a road;
- lines M+2, . . . , M+K+1 contain an integer, p_i (0<p_i<=M), followed by p_i integers x₁, x₂, ?, x_pi(0<x_j<=M, 0<j<=p_i), representing the number of roads controlled by guild i, and respectively the roads controlled by it. All numbers are separated by a single space. The description of guild i is on line M+i+1. Roads are considered numbered from 1 to M in the order in which they are in the input file. Each road appears exactly once on one of the lines M+2, . . . , M+K+1.

Output Data

Line one of output file sol.out must contain a positive integer D, representing the number of selected roads or -1 if there is no solution. If there is a solution, the following line must contain D integers each separated by a single space, representing the selected roads. Roads are considered numbered from 1 to M in the order in which they are in the input file. The order in which the roads are displayed does not matter. If there is more than one solution, then any solution is deemed correct.

Restrictions

• 0 <= N,M <= 200
• 0 <= K <= M
• There is no road from a city to itself.
• Between any two cities there is at most one road.

Example

Time limit: 0.1 seconds/test

student Codrut Grosu
Automatics and Computer Department, Polytechnic University of Bucharest
grosu_codrut@yahoo.com