KZBLK - ABC Blocks

no tags 

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

hide comments
nadstratosfer: 2018-06-14 05:48:42

5.5 years without solvers. An useful tutorial problem thrown into oblivion due to lack of tags :(

Vertexes in the graph are numbered 1..11 as in the statement.

Maciej Grzymkowski: 2012-10-10 20:52:11

Please also note: the sequence of results does matter

[Trichromatic] XilinX: 2009-09-29 04:30:12

All the input integers don't exceed 20.


Added by:balaji
Date:2009-09-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL NODEJS PERL6 VB.NET
Resource:kruzade 09 mains