Road Construction

Description:

Input:

Input begins with a line containing two integers: $$$N$$$ $$$K$$$ ($$$3 \le N \le 2000$$$; $$$1 \le K \le 2000$$$) representing the number of cities and the number of workers, respectively. The next $$$N$$$ lines each contains several integers: $$$A_i$$$ $$$M_i$$$ $$$(B_i)_1$$$, $$$(B_i)_2$$$, $$$\cdots$$$, $$$(B_i)_{M_i}$$$ ($$$1 \le A_i \le N$$$; $$$A_i \ne i$$$; $$$1 \le M_i \le 10\,000$$$; $$$0 \le (B_i)_1 < (B_i)_2 < \dots < (B_i)_{M_i} \le 10^9$$$) representing the bidirectional road that city $$$i$$$ likes to construct. It is guaranteed that the sum of $$$M_i$$$ does not exceed $$$10\,000$$$. It is also guaranteed that no two cities like to connect with each other and any pair of cities are connected by a sequence of road proposals. The next line contains $$$K$$$ integers: $$$C_i$$$ ($$$0 \le C_i \le 10^9$$$) representing the material that is familiarized by the workers.

Output:

If it is not possible to assign each worker to construct a road such that any pair of cities are connected by a sequence of constructed road, simply output -1 in a line. Otherwise, for each worker in the same order as input, output in a line two integers (separated by a single space): $$$u$$$ and $$$v$$$ in any order. This means that the worker constructs a direct bidirectional road connecting city $$$u$$$ and $$$v$$$. If the worker does not construct any road, output "0 0" (without quotes) instead. Each pair of cities can only be assigned to at most one worker. You may output any assignment as long as any pair of cities are connected by a sequence of constructed road.

Sample Input:

4 5
2 2 1 2
3 2 2 3
4 2 3 4
2 2 4 5
1 2 3 4 5

Sample Output:

1 2
2 3
3 4
0 0
4 2

Sample Input:

4 5
2 2 10 20
3 2 2 3
4 2 3 4
2 2 4 5
1 2 3 4 5

Sample Output:

-1

Note:

Explanation for the sample input/output #1

We can assign the workers to construct the following roads:

• The first worker constructs a road connecting city $$$1$$$ and city $$$2$$$.
• The second worker constructs a road connecting city $$$2$$$ and city $$$3$$$.
• The third worker constructs a road connecting city $$$3$$$ and city $$$4$$$.
• The fourth worker does not construct any road.
• The fifth worker constructs a road connecting city $$$4$$$ and city $$$2$$$.

Therefore, any pair of cities are now connected by a sequence of constructed road.

Explanation for the sample input/output #2

There is no worker that can construct a road connecting city $$$1$$$, thus city $$$1$$$ is certainly isolated.