시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

Artem came to a circus, and now he is going to take part in the magic trick.

Artem secretly chooses permutation --- an array of $n$ distinct integers from $1$ to $n$. Let the chosen permutation be $[a_1, a_2, \ldots, a_n]$. For every $i$ from $1$ to $n$ Artem takes the set $\{a_i, a_{i+1}, a_{i+2}\}$ (we assume that $a_{n+1} = a_1$, $a_{n+2} = a_2$).

He shuffles the elements of each set, and then shuffles the sets themselves. After that he  reports the resulting sets to the Magician.

You are that Magician. You need to figure out the permutation Artem has chosen.

입력

The first line contains an integer $n$ ($3 \le n \le 200\,000$), the number of elements in the permutation.

Each of the following $n$ lines contains three distinct integers $a_{i,1}, a_{i,2}, a_{i,3}$ ($1 \le a_{i,j} \le n$), the sets that Artem has reported to the Magician.

It's guaranteed, that the Artem's sets correspond to at least one valid permutation.

출력

Print the permutation of $n$ elements Artem has secretly chosen.

If there are several possible permutations that can lead to the given sets of triples, print any suitable permutation.

예제 입력 1

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

예제 출력 1

1 3 4 2 5 6

예제 입력 2

3
1 2 3
2 3 1
1 2 3

예제 출력 2

1 2 3

힌트

In the second example, you can print any permutation of $1$, $2$ and $3$.