The school aims to recreate a feast such as this.

It is almost Thanksgiving at Pierre Elliott Trudeau High School! (The school celebrates it around 1-2 weeks after the actual date). In order to truly celebrate Thanksgiving, TSAC (Trudeau Student Activity Council) has decided to host a huge Thanksgiving feast.

$N$ students (numbered from $1$ to $N$) will eat at the feast. There are $N$ chairs bolted in place, lined up in a row; each chair will be occupied by a single student. There are also $N$ dishes (numbered from $1$ to $N$); dishes can only be placed directly in front of a chair and exactly one dish must be placed in front of a chair.

Each student has a list of dishes that they would like to eat from. In particular, the $i^{\text{th}}$ student wants to eat from $d_i$ specific dishes. When the feast begins, all of the students begin eating and they must reach out their arms for the various dishes around them. Students will always reach straight for a dish (i.e. they will not bend their arm around anything). However, it is considered to be uncivil if two or more students might cross their arms when getting their food. Note that arms do not cross at the dishes themselves, meaning that multiple students can eat from the same dish.

You have been tasked to choose the order to place the students and the dishes. Can you find a way to order the students and dishes so that it is impossible for any two students to cross their arms?

Constraints

For all subtasks:

$0\le d_i\le N$

The sum of all $d_i$ will not exceed ${10}^6$.

Subtask 1 [25%]

$1\le N\le 5$

Subtask 2 [25%]

$1\le N\le 1000$

Additionally, if there is a solution, it is possible to place the $i^{\text{th}}$ dish directly in front of the $i^{\text{th}}$ chair. In other words, if any solution exists, at least one solution will have the order of the dishes as $1,2,\dots ,N$.

Subtask 3 [50%]

$1\le N\le 100000$

Input Specification

The first line will contain $N$.

$N$ lines of input follow. The $i^{\text{th}}$ line will first contain an integer, $d_i$, the number of dishes the $i^{\text{th}}$ student wants. $d_i$ space-separated integers will follow, specifying the dishes that the $i^{\text{th}}$ student would like to eat from, in increasing order.

Output Specification

If there is a way to arrange the students and the dishes such that no two students can cross their arms, output two lines of $N$ space-separated integers each: the order of the students on the first line and the order of the dishes on the second line. If there are multiple answers, output any one of them.

If there is no valid arrangement, output every man for himself!.

Sample Input 1

2
2 1 2
1 1

Sample Output 1

1 2
2 1

Explanation for Sample Output 1

If the dishes are ordered 1,2 and the ordering of the students is 1,2, the two students would cross arms if student 1 reaches for dish 2 at the same time student 2 reaches for dish 1.

If the dishes are ordered 2,1 and the ordering of the students is 1,2, the two students will never be able to cross arms. Note that the two students are allowed to reach for dish 1 at the same time.

Sample Input 2

3
2 2 3
2 1 3
2 1 2

Sample Output 2

every man for himself!

Sample Input 3

3
1 1
2 1 2
2 1 3

Sample Output 3

2 1 3
2 1 3