CF1252L Road Construction

在 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$ 的道路。每个工人最多只能修建一条道路。你需要为每个工人分配道路，使得任意一对城市都可以通过若干已建道路连通。

输入的第一行包含两个整数：$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 < (B_i)_2 < \dots < (B_i)_{M_i} \le 10^9$），表示城市 $i$ 提议修建的双向道路。保证所有 $M_i$ 之和不超过 $10\,000$。保证没有两个城市互相喜欢对方，且任意一对城市都可以通过若干提议的道路连通。接下来一行包含 $K$ 个整数：$C_i$（$0 \le C_i \le 10^9$），表示每个工人熟悉的材料。

如果无法为每个工人分配道路，使得任意一对城市都可以通过若干已建道路连通，则输出一行 -1。否则，对于每个工人，按输入顺序输出一行两个整数（用一个空格分隔）：$u$ 和 $v$，表示该工人修建了一条直接连接城市 $u$ 和 $v$ 的双向道路，顺序不限。如果该工人没有修建任何道路，则输出“0 0”。每对城市最多只能被分配给一个工人。只要任意一对城市都可以通过若干已建道路连通，你可以输出任意一种分配方案。

样例输入输出 #1 说明 我们可以为工人分配如下道路： - 第一个工人修建连接城市 $1$ 和城市 $2$ 的道路。 - 第二个工人修建连接城市 $2$ 和城市 $3$ 的道路。 - 第三个工人修建连接城市 $3$ 和城市 $4$ 的道路。 - 第四个工人没有修建任何道路。 - 第五个工人修建连接城市 $4$ 和城市 $2$ 的道路。 因此，任意一对城市都可以通过若干已建道路连通。 样例输入输出 #2 说明 没有工人能够修建连接城市 $1$ 的道路，因此城市 $1$ 必然是孤立的。 由 ChatGPT 4.1 翻译