P6983 [NEERC 2015] King’s Inspection

国王 Karl 是一位负责且勤勉的统治者。每年他都会在全国各地巡游，以确保所有城市都运转良好。 他的国家有 $n$ 个城市和 $m$ 条道路。为了控制旅行者，每条道路都是单向的，即从城市 $a$ 到城市 $b$ 的道路不能从 $b$ 到 $a$ 通过。 Karl 想要沿着这些道路旅行，他希望从首都出发，恰好访问每个非首都城市一次，并最终回到首都。 作为交通部长，你有责任找到这样一条路线，或者确定这样的路线不存在。

第一行包含两个整数 $n$ 和 $m$ $(2 \le n \le 100000, 0 \le m \le n + 20)$ —— 国家中的城市数量和道路数量。 接下来的 $m$ 行中的每一行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \le a_{i}, b_{i} \le n)$，表示有一条从城市 $a_{i}$ 到城市 $b_{i}$ 的单向道路。城市编号从 $1$ 到 $n$。首都编号为 $1$。

如果存在一条路线可以恰好经过每个非首都城市一次，并且起点和终点都是首都，则输出 $n + 1$ 个以空格分隔的整数——表示沿途经过的城市列表。请在路线的开头和结尾都输出首都城市。 如果没有符合条件的路线，则输出 `There is no route, Karl!`（不带引号）。

时间限制：10 秒，内存限制：512 MB。 题面翻译由 ChatGPT-4o 提供。