406404: GYM102396 I Magic Trick
Description
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.
InputThe 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.
OutputPrint 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.
ExamplesInput6 3 4 1 5 1 6 5 4 2 2 4 3 2 5 6 6 1 3Output
1 3 4 2 5 6Input
3 1 2 3 2 3 1 1 2 3Output
1 2 3Note
In the second example, you can print any permutation of $$$1$$$, $$$2$$$ and $$$3$$$.