You are the mayor of the big city and your task is to build the cheapest transport system to satisfy all residents.

There are n junctions in the city. Total of q residents live in this city. All of them are really hardworking - so they need public transport only for moving from home to work and returning back. The home of the i-th resident is located at the $a_i$-th junction and the place where he works is located at the $b_i$-th junction.

Also your assistant has prepared a detailed plan of all possible speed tram routes in the city. There are $m$ possible tram routes. The i-th of them contains $cnt_i$ possible stops on the junctions $s_{i, 1}, ... , s_{i, cnt_i}$, and you have to spend $p_i$ dollars to build it.

Taxes in the city are so high that all tickets are free for residents. And residents in this city are so patient that they can change trams as many times as they need to reach work. Because of this your task is just to build such tram system that every resident can reach his work. For every route, once you build it, residents can board and leave tram at every stop of this route. Also if there are several tram lines going through some junction residents can use any of them in any direction once they reached the junction. Residents can't go between stops by foot because they can't work during walk.

Note that for you the order of stops in the plan is not important.

It is guaranteed that it is possible to build such set of routes that all residents will be satisfied.

Input format

The first line of input contains three space separated integers n, m and q ($1 \leq n \leq 10^5, 1 \leq m \leq 10^4, 1 \leq q \leq 10^4$) - the number of junctions, the number of possible tram lines and the number of residents.

Next m lines contain information about possible tram routes. The i-th of them contains the integer $p_i$ ($1 \leq p_i \leq 10^9$) - the cost of the i-th route, the integer $cnt_i$ - the number of possible stops and then $cnt_i$ integers $s_{i, j}$ ($1 \leq s_{i, j} \leq n$) - the possible stops of this route.

It is guaranteed that $\sum_{i=1}^{m}cnt_i \leq 10^6$.

Next q lines contain information about residents. The i-th of them contains two space separated integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$) - the home and the work junctions numbers of the i-th resident.

Output format

In the first line print the number of routes which you are going to buy.

In the second line print indices (1-based) of routes which you are going to buy.

Your transport system should satisfy all residents of the city.

All printed routes should be pairwise distinct.

Score

This is approximate problem. For each test your solution will receive score equal to $\log(sum) \cdot 10^6$, where $sum$ is sum of costs of printed routes. Your task is to minimize this score.

Tests

There are two types of tests:

1. Just city roads. In tests of this group, there are several connected components by routes. Routes have random size according to type of each route (small or large).
2. Highway and city roads. In tests from this group, there are two networks. One of them doesn't contain any $a_i$ or $b_i$ (highway). Also between networks there are several connections.