Maximum Reachable Node

You are given a directed graph with N nodes and M edges. The nodes are numbered from 1 to N. For every node v, define A(v) as the maximum numbered node that is reachable from v (including v itself). Two nodes are considered reachable if there exists a path from one to the other following the direction of the edges. Your task is to compute A(v) for each v from 1 to N.

Note: The graph can contain cycles. To solve the problem efficiently, you may need to perform a strongly connected components decomposition and work on the resulting Directed Acyclic Graph (DAG).

The mathematical formulation is as follows:

where \(v \to^* u\) denotes that there is a directed path from v to u.

inputFormat

The first line contains two integers N and M representing the number of nodes and edges respectively.

The following M lines each contain two integers u and v representing a directed edge from node u to node v.

outputFormat

Output a single line containing N integers separated by spaces, where the i-th integer denotes the value of A(i).

sample

4 4
1 2
2 3
3 4
4 2

4 4 4 4