题目描述

题目译自 XXXI Olimpiada Informatyczna – II etap Telefony

在 Bajtocja 这个国度，城市通过精简的双向道路网络相连，确保任意两城之间有且仅有一条不重复的路径。每座城市至少居住着一位居民。

每位 Bajtocja 居民都拥有手机，并存储了特定联系人的电话号码：包括同城所有其他居民，以及与所在城市直接相连的邻城所有居民的号码，且仅限于这些号码。

你供职于 Bajtocja 移动通信公司，掌握了所有居民手机中的联系人信息。你的任务是根据这些信息，重构 Bajtocja 的道路网络，并确定每位居民居住的城市。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 500000)$，表示 Bajtocja 居民总数，居民编号从 $1$ 到 $n$。

接下来的 $n$ 行，第 $i$ 行描述第 $i$ $(1 \leq i \leq n)$ 位居民的联系人列表：以一个非负整数 $k_i$ 开头，后跟 $k_i$ 个严格递增的整数，范围从 $1$ 到 $n$，表示存储的联系人编号。若列表包含 $j$，则居民 $i$ 有居民 $j$ 的电话号码。保证列表不包含 $i$ 自身。

记 $p = k_1 + k_2 + \ldots + k_n$ 为所有居民存储的电话号码总数，满足 $0 \leq p \leq 1000000$。

输出格式

第一行输出一个整数 $m$，表示 Bajtocja 城市数量，城市编号从 $1$ 到 $m$。

第二行输出 $n$ 个整数，范围从 $1$ 到 $m$，以空格分隔，第 $i$ $(1 \leq i \leq n)$ 个数表示居民 $i$ 居住的城市编号。

接下来的 $m-1$ 行，每行包含两个不同整数 $a, b$ $(1 \leq a, b \leq m)$，以空格分隔，表示城市 $a$ 和 $b$ 之间存在道路。

若存在多种解，输出城市数量 $m$ 最大的解。若 $m$ 最大时仍有多种解，输出任意一种。

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

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

在图示中，圆圈表示城市，线条表示道路，圆圈上方的数字是城市编号，圆圈内的数字是各城市居民的编号。

附加样例

1. $m=7$，城市形成满二叉树，第 $i$ $(1 \leq i \leq 7)$ 座城市有 $i$ 名居民。
2. $n=500$，城市形成星形网络，每座城市有 $1$ 名居民。
3. $n=500000$，城市形成路径网络，每座城市有 $1$ 名居民。

数据范围与提示

详细子任务附加限制及分值如下表所示。

若仅第一行（城市数量 $m$）正确，程序可获 $50\%$ 的分数。