Bajtocji 的城市由一个经济的双向道路网络连接。更准确地说，从任意一个城市到另一个城市，通过道路网络有且仅有一种不折返的路径。每个城市至少有一名居民。

Bajtocji 的每位居民都有一部手机。每位居民的手机里都存有其所在城市的所有其他居民的电话号码，以及与他所在城市直接相连的每个城市的所有居民的电话号码。我们假设这些是每位居民手机中仅有的电话号码。

你在 Bajtocji 电信公司工作，已知每位居民手机中存储的电话号码。你的任务是重建 Bajtocji 的道路网络，并确定每位居民居住在哪个城市。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示 Bajtocji 的居民人数。居民编号为 $1$ 到 $n$。接下来的 $n$ 行中，第 $i$ 行描述了第 $i$ 位居民存储的电话号码 ($1 \le i \le n$)。描述以一个非负整数 $k_i$ 开头，随后是 $k_i$ 个范围在 $1$ 到 $n$ 之间的严格递增的整数。如果序列中包含数字 $j$，则表示第 $i$ 位居民存储了第 $j$ 位居民的电话号码。你可以假设在描述第 $i$ 位居民的序列中不会出现数字 $i$。

令 $p = k_1 + k_2 + \dots + k_n$ 表示所有居民手机中存储的电话号码总数。满足 $0 \le p \le 1\,000\,000$。

输出格式

输出的第一行应包含一个整数 $m$，表示 Bajtocji 的城市数量。假设城市编号为 $1$ 到 $m$。第二行应包含一个由 $n$ 个范围在 $1$ 到 $m$ 之间的整数组成的序列，并用空格分隔；其中第 $i$ 个数字（对于 $1 \le i \le n$）表示第 $i$ 位居民居住的城市编号。接下来的 $m-1$ 行应描述城市间的道路连接。每条连接应由两个不同的整数 $a$ 和 $b$ ($1 \le a, b \le m$) 描述，并用空格分隔，表示连接这两个城市。

如果存在多种可能的答案，请输出城市数量 $m$ 最大的那种。如果存在多个具有最大 $m$ 的答案，你可以输出其中任意一个。

样例

输入 1

8
3 2 4 6
4 1 4 6 7
2 5 7
3 1 2 6
2 3 7
4 1 2 4 7
5 2 3 5 6 8
1 7

输出 1

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

图中圆圈表示城市，连线表示道路，圆圈上方的数字为城市编号，圆圈内的数字为居住在该城市的居民编号。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。

如果你的程序仅正确输出了输出的第一行，则该测试用例可获得 50% 的分数。在这种情况下，后续输出行的内容可以是任意的。