The cities in Byteland are connected by an economical network of bidirectional roads. Specifically, there is exactly one path between any two cities that does not involve backtracking. Each city has at least one inhabitant.

Every inhabitant of Byteland has a mobile phone. Each inhabitant has the phone numbers of all other inhabitants living in the same city, as well as all inhabitants of every city that is directly connected to their city by a road. We assume these are the only phone numbers that each inhabitant has saved.

You work at the Byteland Mobile Telephony company and you know which phone numbers are saved in the phones of each inhabitant of Byteland. Your task is to reconstruct the road network of Byteland and determine, for each inhabitant, which city they live in.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 500\,000$), representing the number of inhabitants of Byteland. The inhabitants are numbered from $1$ to $n$. The $i$-th of the following $n$ lines contains a description of the phone numbers stored by the $i$-th inhabitant ($1 \le i \le n$). The description starts with a non-negative integer $k_i$, followed by a strictly increasing sequence of $k_i$ integers in the range from $1$ to $n$. If the number $j$ appears in this sequence, it means that the $i$-th inhabitant has the phone number of the $j$-th inhabitant saved. You may assume that the number $i$ does not appear in the sequence describing the $i$-th inhabitant.

Let $p = k_1 + k_2 + \dots + k_n$ be the total number of phone numbers saved in the phones of the inhabitants of Byteland. It holds that $0 \le p \le 1\,000\,000$.

Output

The first line of the output should contain a single integer $m$, representing the number of cities in Byteland. We assume that the cities are numbered from $1$ to $m$. The second line should contain a sequence of $n$ integers in the range from $1$ to $m$ separated by single spaces; the $i$-th number in this sequence (for $1 \le i \le n$) denotes the number of the city where the $i$-th inhabitant lives. The following $m-1$ lines should contain the description of the road connections between the cities. Each connection should be described by two distinct integers $a$ and $b$ ($1 \le a, b \le m$) separated by a single space, representing the numbers of the cities between which the road connection runs.

If there are multiple possible answers, output one where the number of cities $m$ is maximized. If there are multiple possible answers with the maximum $m$, you may output any one of them.

Examples

Input 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

Output 1

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

Note

In the figure, circles represent cities, lines represent roads, numbers above the circles are city numbers, and numbers inside the circles are the numbers of the inhabitants of the respective cities.

Sample tests

Test 0 is the test from the example above. Additionally:

• 1ocen: $m = 7$ cities form a full binary tree; the $i$-th city has $i$ inhabitants ($1 \le i \le 7$)
• 2ocen: $n = 500$, star graph, each city has one inhabitant
• 3ocen: $n = 500\,000$, path graph, each city has one inhabitant

Scoring

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

If your program outputs only the first line of the output correctly, it will receive 50% of the points for the given test. In this case, the content of the subsequent lines of the output can be arbitrary.