Description

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

Format

Input

第 1 行，2 个整数 N,M。 接下来 M 行，每行 2 个整数 Ui,Vi，表示边 ⟨Ui,Vi⟩。点用 1,2,...,N 编号。

Output

N 个整数 A(1),A(2),...,A(N)。

Sample 1

Input

4 3
1 2
2 4
4 3

Output

4 4 3 4

Limitation

1000ms, 256mb for each test case.

Hint

对于 60% 的数据，1 ≤ N,K ≤ 10^3
对于 100% 的数据，1 ≤ N,M ≤ 10^5。