CF1252L.Road Construction

There are $N$ cities in the country of Numbata, numbered from $1$ to $N$. Currently, there is no road connecting them. Therefore, each of these $N$ cities proposes a road candidate to be constructed.

City $i$ likes to connect with city $A_i$, so city $i$ proposes to add a direct bidirectional road connecting city $i$ and city $A_i$. It is guaranteed that no two cities like to connect with each other. In other words, there is no pair of integers $i$ and $j$ where $A_i = j$ and $A_j = i$. It is also guaranteed that any pair of cities are connected by a sequence of road proposals. In other words, if all proposed roads are constructed, then any pair of cities are connected by a sequence of constructed road.

City $i$ also prefers the road to be constructed using a specific material. Each material can be represented by an integer (for example, $0$ for asphalt, $1$ for wood, etc.). The material that can be used for the road connecting city $i$ and city $A_i$ is represented by an array $B_i$ containing $M_i$ integers: $[(B_i)_1, (B_i)_2, \dots, (B_i)_{M_i}]$. This means that the road connecting city $i$ and city $A_i$ can be constructed with either of the material in $B_i$.

There are $K$ workers to construct the roads. Each worker is only familiar with one material, thus can only construct a road with a specific material. In particular, the $i^{th}$ worker can only construct a road with material $C_i$. Each worker can only construct at most one road. You want to assign each worker to construct a road such that any pair of cities are connected by a sequence of constructed road.

Numbata 国有 $N$ 座城市，编号从 $1$ 到 $N$。目前，这些城市之间没有任何道路相连。因此，每座城市均提出一条待修建的道路候选方案。

城市 $i$ 希望与城市 $A_i$ 相连，因此城市 $i$ 提出修建一条连接城市 $i$ 与城市 $A_i$ 的双向直连道路。保证不存在两座城市彼此互为偏好对象，即：不存在整数对 $(i, j)$ 满足 $A_i = j$ 且 $A_j = i$。同时保证：若将所有提出的道路全部修建，则任意两座城市均可通过若干条已建道路相互连通（即所有道路构成的图是连通的）。

此外，城市 $i$ 还倾向于使用某种特定材料来修建该道路。每种材料可用一个整数表示（例如，$0$ 表示沥青，$1$ 表示木材等）。用于修建连接城市 $i$ 与城市 $A_i$ 的道路的可选材料由数组 $B_i$ 给出，其中包含 $M_i$ 个整数：$[(B_i)_1, (B_i)_2, \dots, (B_i)_{M_i}]$。这意味着连接城市 $i$ 与城市 $A_i$ 的道路可选用 $B_i$ 中任意一种材料建造。

共有 $K$ 名工人负责修建道路。每位工人仅熟悉一种材料，因此只能修建使用该特定材料的道路。具体而言，第 $i$ 位工人仅能修建材料为 $C_i$ 的道路。每位工人最多只能修建一条道路。你的目标是为每位工人分配一条道路进行修建，使得最终修建的道路集合仍能保证任意两座城市均可通过若干条已建道路相互连通。

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 \lt (B_i)_2 \lt \dots \lt (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.

输入的第一行包含两个整数：$N$ 和 $K$（$3 \le N \le 2000$；$1 \le K \le 2000$），分别表示城市的数量和工人的数量。接下来的 $N$ 行，每行包含若干个整数：$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 \lt (B_i)_2 \lt \dots \lt (B_i)_{M_i} \le 10^9$），表示城市 $i$ 希望建造的一条双向道路。保证所有 $M_i$ 的总和不超过 $10\,000$。同时保证任意两座城市之间至多存在一条彼此希望连接的道路，且任意两座城市均可通过一系列道路提案相互连通。下一行包含 $K$ 个整数：$C_i$（$0 \le C_i \le 10^9$），表示各工人所熟悉的材料。

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.

如果无法为每位工人分配一条道路，使得任意两座城市之间都可通过已修建的道路序列相互连通，则直接在一行中输出 -1。否则，对于输入中给出的每位工人（按相同顺序），在一行中输出两个整数（用单个空格分隔）：$u$ 和 $v$（顺序任意），表示该工人修建一条连接城市 $u$ 和 $v$ 的双向直连道路；若该工人不修建任何道路，则输出 0 0（不带引号）。每对城市至多只能被分配给一位工人。只要最终所有城市构成连通图，可输出任意一种满足条件的分配方案。

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.

样例输入/输出 #1 的说明

我们可以安排工人修建以下道路：

• 第一位工人修建连接城市 $1$ 和城市 $2$ 的道路。
• 第二位工人修建连接城市 $2$ 和城市 $3$ 的道路。
• 第三位工人修建连接城市 $3$ 和城市 $4$ 的道路。
• 第四位工人不修建任何道路。
• 第五位工人修建连接城市 $4$ 和城市 $2$ 的道路。

因此，任意两个城市之间现在均可通过一系列已修建的道路相互连通。

样例输入/输出 #2 的说明

没有任何工人能够修建连接城市 $1$ 的道路，因此城市 $1$ 必然孤立。