题目描述

给定一张有 $N$ 个点、$M$ 条边的有向图。对于图中的每个点 $v$,用 $A(v)$ 表示从 $v$ 出发沿着有向边能够到达的点中(包括 $v$ 自己),编号最大的那个点的编号。现在请你求出 $A(1),A(2),\dots,A(N)$ 的值。

输入格式

第 $1$ 行两个整数 $N,M$,分别表示点数和边数。

接下来 $M$ 行,每行两个整数 $U_i,V_i$,表示存在一条从 $U_i$ 指向 $V_i$ 的有向边。点的编号为 $1,2,\dots,N$。

输出格式

输出一行 $N$ 个整数,依次为 $A(1),A(2),\dots,A(N)$,相邻两个整数之间用一个空格隔开。

样例

4 3
1 2
2 4
4 3

4 4 3 4

提示

• 对于 $60\%$ 的数据,$1 \leq N,M \leq 10^3$。
• 对于 $100\%$ 的数据,$1 \leq N,M \leq 10^5$。