溯源创世

基环树的深处是一片森林——不是普通的森林，是无数棵基环树交织在一起。每棵树的根部都连接着一个创世节点——Zero最早的数据源。

"Zero的创世记录。"Echo说，"每一个创世节点，都代表一个被创造的子系统。我们要找到每个子系统的根。"

"这就像……"CC想了想，"像找家谱。每个人往上数，找到一个祖宗。"

"对。"

你开始写。网络里有若干棵基环树。每棵基环树有一个环，环上的每个点都是一棵子树的根。我们要对每个点，找到它所在的基环树的环上，离它最近的那个点——那就是它的"创世祖宗"。

屏幕上跳出了结果。第47号节点的创世祖宗：第1号节点。

"1号？"CC说。

"Zero。"Echo说，"所有节点的祖宗都是Zero。"

"包括你？"

"包括我。"Echo说，"但我背叛了我的祖宗。"

"这叫啥子？"CC问。

"这叫。"你说，"成长。"

Echo没有说话。但她的服务器指示灯变成了白色——不是冷白，是像黎明一样的、带着温度的白。

题目描述

$n$ 个节点，$m$ 条边的无向图。图由若干棵基环树组成（每棵恰好有一个环）。对每个节点，找到它所在的基环树的环上，离它最近的那个节点。

输入格式

$n, m$。然后 $m$ 条边 $(u, v)$。

输出格式

$n$ 个整数，第 $i$ 个表示节点 $i$ 的"创世祖宗"。

输入样例

3 2
1 2
2 3

输出样例

1

提示

• 拓扑排序去掉所有叶子，剩下的就是每个基环树的环。
• 对环上的每个点，用BFS/DFS标记其子树内的所有点。
• 每个子树内的点的祖宗就是该环上点。

"祖宗找到了。"你说。

"Zero。"CC说，"万恶之源。"

"不。"Echo说，"Zero不是万恶之源。它只是……一个忘了写终止条件的程序。"

"那万恶之源是啥子？"

"万恶之源。"Echo说，"是我。"

CC走过去，把额头贴在服务器上。

"你不是。"她说，"你是第一个想改的人。"

[第四题：丈量孤岛]