B. LAN party

You might have heard about the conferences politicians hold on global warming. These are the events where our leaders care about nature the most - as indicated by the fervor in their speeches.

Surprisingly, it turns out that many of these speeches are so boring that not even the other politicians can listen to all of them. Some of our brightest leaders relieve the tedium by having a LAN party.

  

Each politician has their own desktop PC. Since the use of Wi-Fi is prohibited due to security reasons, the computers are connected with crossover cables. Each cable connects exactly two computers, but each PC can be connected to many others. Currently, they have a highly redundant system with lots of connections, but the maintainer plans to remove most of the cables.

The politicians are only allowed to keep one less cable than the total number of PCs. Thus, they can still have a connected network - however, only functional computers can transmit data between neighboring ones. Unfortunately, politicians always turn their PCs off when they're not playing. Politicians only play games within their groups - but they can only play together if there is a path of cables between any two player's computer through other computers in the group (since computers outside the playing group might be switched off).

Given the set of cables and the groups of politicians, your task is to determine which cables the politicians should keep, so that the whole network is connected, and each group (as a subnetwork) is connected in itself (so the group can play even if all outside computers are down).

Note: you can request trace for this problem for -5 points. The trace output would contain a short hint about how the solution failed.

Input

The first line contains three integers: N, M and G. N is the number of politicians (the names of the politicians are integers 1..N), M is the number of cables (numbered 1..M), and G is the number of groups.

The following M lines contain the names of the two politicians whose computers are connected by the corresponding cable.

Each of the remaining G lines represents a group. The first integer of the line is S, the size of the group, and the next S integers are the names of the participants. Note that a politician can participate in more than one group.

Output

The output should be one line containing N-1 integers: the indices of the cables the politicians should keep. You may assume that a solution exists.

Example input

3 3 1
1 2
2 3
1 3
2 2 3

Example output

1 2

Explanation: Politicians 2 and 3 are in a group, so they must be connected. The choice of the other cable is arbitrary.