Eulerian Circuit with Mandatory Sequences

In a city, all roads are one‐way (directed) and connect various intersections numbered from 1 to n. There is at most one road in each direction between any two intersections. A postman starts and ends his route at intersection 1. He must traverse every road exactly once (i.e. find an Eulerian circuit). Recently, new regulations require that his route must also contain several prescribed sequences of intersections as contiguous subsequences. For example, if the required sequence is 1 2 1, then the route 1 2 1 3 is acceptable, but 1 2 3 1 is not, because the sequence does not appear consecutively.

Your task is to determine whether there exists a route satisfying all these conditions. If so, output one such route. Otherwise, output -1.

Note: If a route exists, it must be an Eulerian circuit in the given directed graph that also contains every given intersection sequence as a contiguous fragment.

The problem may be solved using backtracking (since the input sizes are small) to generate an Eulerian circuit and then checking the additional contiguous sequence constraints.

inputFormat

The first line contains three integers n, m, k where n is the number of intersections, m is the number of roads, and k is the number of required sequences.

The next m lines each contain two integers u and v describing a directed road from intersection u to intersection v.

Then k blocks follow. Each block begins with an integer L indicating the length of a required sequence, followed by L integers representing the sequence of intersections.

You can assume that the graph is small enough for a backtracking solution to pass.

outputFormat

If such a route exists, output the sequence of intersections (separated by spaces) representing a valid Eulerian circuit that starts and ends at intersection 1 and contains each required sequence as a contiguous subsequence. If no valid route exists, output -1.

sample

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

1 2 3 1 4 3 1