题目描述

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.

输入格式

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

Each of the next $m$ lines contains two integers $a_{i}$ and $b_{i} (1 \le a_{i}, b_{i} \le n)$ , meaning that there is a one-way road from city $a_{i}$ to city $b_{i}.$ Cities are numbered from $1$ to $n$ . The capital is numbered as $1$ .

输出格式

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).

题目大意

国王 Karl 是一个负责并且勤奋的统治者。每年他都会游览并视察他的国家来保证每个城市都欣欣向荣。

他的国家有$n$个城市$m$条道路。每条道路是单向的，一条$a$到$b$的道路不能由$b$到$a$ 经过。

Karl 想要游览他的国家，并且路线为由首都开始，经过每个非首都城市恰好一次，最终回到首都。

作为运输大臣，你有义务找到这样的一条路线，或者确定其不存在。

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!

提示

Time limit: 10 s, Memory limit: 512 MB.