题目描述

Numbata 国共有 $N$ 座城市，编号为 $1$ 到 $N$。

目前城市之间没有任何道路，因此每座城市都提出了一条候选道路。

城市 $i$ 希望与城市 $A_i$ 相连，于是它提议修建一条连接城市 $i$ 与城市 $A_i$ 的双向道路。

保证不存在两座城市互相提出连接请求。也就是说，不存在 $i,j$ 满足：

$$A_i=j$$

且

$$A_j=i.$$

同时保证，如果把全部候选道路都修建出来，任意两座城市之间都能够通过若干道路互相到达。

每座城市还对自己提出的道路允许使用的材料有要求。

材料用一个整数表示，例如：

• $0$ 可以表示沥青；
• $1$ 可以表示木材；
• 其他整数表示其他材料。

城市 $i$ 提议的道路 $(i,A_i)$ 可以使用的材料集合为：

$$B_i= [(B_i)_1,(B_i)_2,\ldots,(B_i)_{M_i}].$$

共有 $K$ 名工人负责修路。

每名工人只熟悉一种材料，因此只能修建使用该材料的道路。第 $i$ 名工人熟悉的材料为 $C_i$。

每名工人最多修建一条道路。

你需要为工人分配候选道路，使修建完成后，任意两座城市之间都能通过已建道路互相到达。

一条候选道路最多只能分配给一名工人。

不要求所有工人都参与施工。

输入格式

第一行包含两个整数 $N,K$：

$$3\le N\le2000,$$ $$1\le K\le2000,$$

分别表示城市数量和工人数量。

接下来 $N$ 行，第 $i$ 行描述城市 $i$ 提出的候选道路，格式为：

Ai Mi Bi,1 Bi,2 ... Bi,Mi

其中：

$$1\le A_i\le N,$$ $$A_i\ne i,$$ $$1\le M_i\le10\,000,$$ $$0\le(B_i)_1<(B_i)_2<\cdots<(B_i)_{M_i}\le10^9.$$

保证：

$$\sum_{i=1}^{N}M_i\le10\,000.$$

还保证：

• 不存在两座城市互相提出连接请求；
• 全部候选道路构成的无向图连通。

最后一行包含 $K$ 个整数：

$$C_1,C_2,\ldots,C_K,$$

其中：

$$0\le C_i\le10^9,$$

表示每名工人熟悉的材料。

输出格式

如果不存在合法分配方案，输出一行：

-1

否则，按工人的输入顺序输出 $K$ 行。

第 $i$ 行输出两个整数 $u,v$：

• 若第 $i$ 名工人修建连接城市 $u$ 与 $v$ 的道路，则输出 u v，两端点顺序任意；
• 若第 $i$ 名工人不修建任何道路，则输出：

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 2
2 3
3 4
0 0
4 2

说明

• 第 $1$ 名工人修建道路 $(1,2)$；
• 第 $2$ 名工人修建道路 $(2,3)$；
• 第 $3$ 名工人修建道路 $(3,4)$；
• 第 $4$ 名工人不施工；
• 第 $5$ 名工人修建道路 $(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

输出

-1

说明

没有任何工人能够修建城市 $1$ 提出的道路，因此城市 $1$ 一定会被孤立。