D. Aranara Game (Easy)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nahida is playing a game with her fungi friends, the Aranara, on the branches of the Divine Tree in Sumeru City. On the Divine Tree, there are $$$N$$$ ($$$2 \le N \le 10^5$$$) branches. Initially, Nahida starts at branch $$$a$$$ and the Aranara starts at branch $$$b$$$. In a single turn, Nahida will move from branch $$$a$$$ to $$$nxt_a$$$, and the Aranara will move from branch $$$b$$$ to $$$nxt_b$$$. The game ends when they move to the same position, allowing Nahida to finally catch the Aranara. It is guaranteed that $$$nxt_i \neq i$$$ for all $$$i$$$.

Note that Nahida and the Aranara move at the exact same time, so if in one turn Nahida is going from branch $$$1$$$ to $$$2$$$, and the Aranara is going from branch $$$2$$$ to $$$1$$$, then Nahida will not catch the Aranara.

Since the Aranara enjoy playing around in the beautiful nature of Sumeru, they want the game to never end. Thus, they ask you to find $$$N$$$ ordered pairs $$$(a, b)$$$ such that Nahida will never catch the Aranara. It can be shown that there always exists at least $$$N$$$ such ordered pairs.

Input

Line $$$1$$$: One integer $$$N$$$ ($$$2 \le N \le 10^5$$$).

Line $$$2$$$: $$$N$$$ space separated integers representing the values of $$$nxt$$$, with the $$$i + 1$$$th line representing $$$nxt_i$$$ ($$$1 \le nxt_i \le N, nxt_i \neq i$$$).

Output

Line $$$1 \dots N$$$: $$$N$$$ distinct unordered pairs $$$a$$$ and $$$b$$$ such that $$$b$$$ will never catch $$$a$$$. If there are multiple solutions, output any.

Example
Input
2
2 1
Output
1 2
2 1
Note

$$$2 \le N \le 10^5$$$