努巴塔 国家有 $$$N$$$ 个城市,编号从 $$$1$$$ 到 $$$N$$$。目前,没有道路连接它们。因此,这些 $$$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^{th}$$$工人只能用材料$$$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
4 5 2 2 1 2 3 2 2 3 4 2 3 4 2 2 4 5 1 2 3 4 5
输出 #1
1 2 2 3 3 4 0 0 4 2
输入 #2
4 5 2 2 10 20 3 2 2 3 4 2 3 4 2 2 4 5 1 2 3 4 5
输出 #2
-1
注意
示例输入/输出#1 的说明
我们可以指派工人修建以下道路:
- 第一个工人建造了一条连接城市 $$$1$$$ 和城市 $$$2$$$ 的道路。
- 第二个工人建造一条连接城市 $$$2$$$ 和城市 $$$3$$$ 的道路。
- 第三名工人建造了一条连接城市 $$$3$$$ 和城市 $$$4$$$ 的道路。
- 第四名工人没有修建任何道路。
- 第五个工人建造一条连接城市 $$$4$$$ 和城市 $$$2$$$ 的道路。
示例输入/输出#2 的说明
没有工人可以建造连接城市$$$1$$$的道路,因此城市$$$1$$$肯定是孤立的。