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.
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$$$).
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.
2 2 1
1 2 2 1
$$$2 \le N \le 10^5$$$
| Name |
|---|


