题目描述

给出一张有向图，点的编号为 $1$ 到 $N$。对每个点 $v$，求从 $v$ 出发沿有向边能够到达的点中编号最大的一个。点 $v$ 自身也算可达。

输入格式

第一行两个整数 $N,M$，分别表示点数和边数。接下来 $M$ 行，每行两个整数 $u,v$，表示有向边 $u\to v$。

输出格式

输出一行 $N$ 个整数，第 $v$ 个整数表示点 $v$ 能到达的最大编号。

6 6
1 2
1 3
2 4
3 5
5 4
6 3

5 4 5 4 5 6

数据范围

$1\le N,M\le 10^5$。图可以有环，也可以不连通。

提示

可将边反向，按照点的编号从大到小搜索；一个点首次被访问时确定它的答案。