Description

给定有N 个节点、M 条边的有向图，对每个节点v 都求A (v )，表示从节点v 出发，能到达的编号最大的节点。

Format

Input

第1行包含两个整数$N$ 、$M$ $（1≤N ,M ≤10^5 ）$。接下来的M 行，每行都包含两个整数$Ui$、$Vi$ ，表示边$(Ui ,Vi )$。节点的编号为$1～N$ 。

Output

$N$ 个整数$A(1),A(2),⋯,A(N )$。

Samples

4 3
1 2
2 4
4 3

4 4 3 4