CF681D Gifts by the List

Sasha lives in a big happy family. At the Man's Day all the men of the family gather to celebrate it following their own traditions. There are $ n $ men in Sasha's family, so let's number them with integers from $ 1 $ to $ n $ . Each man has at most one father but may have arbitrary number of sons. Man number $ A $ is considered to be the ancestor of the man number $ B $ if at least one of the following conditions is satisfied: - $ A=B $ ; - the man number $ A $ is the father of the man number $ B $ ; - there is a man number $ C $ , such that the man number $ A $ is his ancestor and the man number $ C $ is the father of the man number $ B $ . Of course, if the man number $ A $ is an ancestor of the man number $ B $ and $ A≠B $ , then the man number $ B $ is not an ancestor of the man number $ A $ . The tradition of the Sasha's family is to give gifts at the Man's Day. Because giving gifts in a normal way is boring, each year the following happens. 1. A list of candidates is prepared, containing some (possibly all) of the $ n $ men in some order. 2. Each of the $ n $ men decides to give a gift. 3. In order to choose a person to give a gift to, man $ A $ looks through the list and picks the first man $ B $ in the list, such that $ B $ is an ancestor of $ A $ and gives him a gift. Note that according to definition it may happen that a person gives a gift to himself. 4. If there is no ancestor of a person in the list, he becomes sad and leaves the celebration without giving a gift to anyone. This year you have decided to help in organizing celebration and asked each of the $ n $ men, who do they want to give presents to (this person is chosen only among ancestors). Are you able to make a list of candidates, such that all the wishes will be satisfied if they give gifts according to the process described above?

N/A

N/A

The first sample explanation: - if there would be no $ 1 $ in the list then the first and the third man's wishes would not be satisfied $ (a_{1}=a_{3}=1) $ ; - if there would be no $ 2 $ in the list then the second man wish would not be satisfied $ (a_{2}=2) $ ; - if $ 1 $ would stay before $ 2 $ in the answer then the second man would have to give his gift to the first man, but he wants to give it to himself $ (a_{2}=2) $ . - if, at the other hand, the man numbered $ 2 $ would stay before the man numbered $ 1 $ , then the third man would have to give his gift to the second man, but not to the first $ (a_{3}=1) $ .