描述

给定一个包含 N 个节点（编号为 1 到 N）和 M 条有向边的有向图。对每个节点 v，定义 A(v) 为从 v 出发通过有向路径能够到达的所有节点中编号最大的那个节点的编号（包括 v 自身）。要求输出 A(1), A(2), ..., A(N)。

输入输出格式

输入

第一行包含两个整数 N 和 M，分别表示节点数和有向边数。 接下来 M 行，每行两个整数 U_i 和 V_i，表示一条从 U_i 指向 V_i 的有向边。

输出

一行，共 N 个整数，依次为 A(1), A(2), ..., A(N)，相邻整数用空格分隔。

样例

4 3
1 2
2 4
4 3

4 4 3 4

限制

• 时间限制：1 秒
• 空间限制：256 MB
• 对于 100% 的数据：1 ≤ N, M ≤ 10^5
• 图中节点编号为 1 到 N，边可能重复或自环（但样例与常规解法均兼容）