题目描述

$A$ 国有 $n$ 个城市（编号为 $1$ \sim $n$ ），城市之间修建了 $m$ 条单向的高速公路。请求出从每个城市能到达的编号最大的城市是哪个城市？

例如下图所示的地图， $1$ $2$ $3$ $4$ $5$ 号城市分别能到达的编号最大的城市为： $3$ $3$ $3$ $5$ $5$ 。

输入

第 $1$ 行有 $2$ 个整数 $n$ 和 $m$ ，分别代表城市数量和高速公路的数量。（ $1≤n≤10^5$ ， $1≤m≤10^5$ ）

接下来 $m$ 行，每行有 $2$ 个整数 $x$ 和 $y$ ，分别代表从 $x$ 号城市到 $y$ 号城市有一条单向的高速公路。（ $1≤x,y≤n$ ）

输出

输出 $n$ 个整数，用空格隔开，分别代表编号为 $1$ $2$ $3$ $4$ $...$ $n$ 的城市，按照给定的数据，能到达的最大编号的城市。

样例

5 7
1 2
2 3
3 1
4 3
5 3
4 5
5 1

3 3 3 5 5