ABC college of technology has a number of blocks which houses a number of academic departments and other facilities.
The following are some of the blocks and the facilities there.

1  a block-admin
2  b block-book depot
3  d block-conf hall
4  f block-canteen
5  i block-industry
6  m block-applied science block
7  n block-management
8  o block-hostel
9  j block-mech block
10 t block-textile block
11 eb bock-computer science block

Each block is denote by a number.Some of these blocks are linked to each other through bridges,to navigate easier.
You are to guide a student from a block to the destination through all possible paths.

Input

The first line consists of a single integer which is the destination.
The following lines each consist of a pair of positive
integers separated by a space and terminated by a new-line. They represent the blocks connected by a bridge.
For example, if 1 2 appears on a line, then there is a bridge between block a and b. The final line consists of a pair of
0's.

Output

Your output must consist of a line for each valid route from the a block to the destination.The blocks must
appear separated by a space, terminated by a new-line. Include only routes which do not pass through any
blocks more than once.

Example

Input:
5
1 2
2 3
1 4
4 5
2 5
3 4
0 0
Output:
1 2 3 4 5
1 2 5
1 4 3 2 5
1 4 5