Problem 3K. King's Inspection

Author:NEERC 2015   Time limit:2 sec
Input file:input.txt   Memory limit:512 Mb
Output file:output.txt  


King Karl is a responsible and diligent ruler. Each year he travels across his country to make certain that all cities are doing well.

There are n cities in his country and m roads. In order to control the travelers, each road is unidirectional, that is a road from city a to city b can not be passed from b to a.

Karl wants to travel along the roads in such a way that he starts in the capital, visits every non-capital city exactly once, and finishes in the capital again.

As a transport minister, you are obliged to find such a route, or to determine that such a route doesn't exist.

Input file format

The first line contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ n + 20) — the number of cities and the number of roads in the country.

Each of the next m lines contains two integers ai and bi (1 ≤ ai, bi ≤ n), meaning that there is a one-way road from city ai to city bi. Cities are numbered from 1 to n. The capital is numbered as 1.

Output file format

If there is a route that passes through each non-capital city exactly once, starting and finishing in the capital, then output n+1 space-separated integers — a list of cities along the route. Do output the capital city both in the beginning and in the end of the route. If there is no desired route, output «There is no route, Karl!» (without quotation marks).


Sample tests

No. Input file (input.txt) Output file (output.txt)
4 6
1 4
4 1
4 2
2 1
3 4
1 3
1 3 4 2 1
4 3
1 4
1 4
2 2
There is no route, Karl!

0.039s 0.008s 15