AT_nikkei2019_qual_d Restore the Tree

有一棵包含 $N$ 个顶点的有根树（请参见注释）。这些顶点编号为 $1$ 到 $N$。除根以外的每个顶点，都有一条从其父节点指向它的有向边。注意，根节点不一定是顶点 $1$。 高桥君在这张图上又添加了 $M$ 条新的有向边。每条新添加的边 $u \rightarrow v$，都是从某个顶点 $u$ 指向其后代顶点 $v$。 现在给出高桥君添加边之后的 $N$ 个顶点、$N-1+M$ 条边组成的有向图。更具体地，给出 $N-1+M$ 对整数 $(A_1, B_1),\ldots,(A_{N-1+M}, B_{N-1+M})$，表示第 $i$ 条边是从顶点 $A_i$ 指向顶点 $B_i$。 请你还原出原来的有根树。

输入通过标准输入给出，格式如下： > $N$ $M$ $A_1$ $B_1$ $\ldots$ $A_{N-1+M}$ $B_{N-1+M}$

请输出 $N$ 行。第 $i$ 行输出一个整数：如果顶点 $i$ 是原树的根，则输出 `0`，否则输出顶点 $i$ 在原树中的父节点编号。 可以证明，原树是唯一确定的。

### 注释 关于“树”及相关图论术语，请参考 [Wikipedia 文章](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))。 ### 约束条件 - $3 \leq N$ - $1 \leq M$ - $N + M \leq 10^5$ - $1 \leq A_i, B_i \leq N$ - $A_i \neq B_i$ - 如果 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$ - 输入的图是通过在 $N$ 个顶点的有根树上，按照题目条件添加 $M$ 条边得到的。 ### 样例解释 1 输入的图如下所示。  可以认为这是在 $1 \rightarrow 2 \rightarrow 3$ 这棵有根树上添加了一条 $1 \rightarrow 3$ 的边。 由 ChatGPT 4.1 翻译