Maximal Reachable Vertex

Given a directed graph with \(N\) vertices and \(M\) edges, for each vertex \(v\) define \(A(v)\) as the maximum numbered vertex reachable from \(v\) (including \(v\) itself). You are required to compute \(A(1), A(2), \dots, A(N)\).

The graph may contain cycles and self-loops. A vertex is considered reachable from itself.

inputFormat

The first line contains two integers \(N\) and \(M\), where \(N\) is the number of vertices and \(M\) is the number of edges.

Each of the next \(M\) lines contains two integers \(u\) and \(v\) indicating a directed edge from vertex \(u\) to vertex \(v\>.

outputFormat

Output \(N\) integers separated by spaces, where the \(i\)-th integer is \(A(i)\) — the maximum numbered vertex reachable from vertex \(i\).

sample

3 3
1 2
2 3
3 1

3 3 3