Description

Given a directed graph with $N$ vertices and $M$ edges, for each vertex $v$, let $A(v)$ denote the reachable vertex with the largest index starting from $v$. Now compute $A(1), A(2), \dots, A(N)$.

Input Format

The first line contains two integers $N, M$, denoting the number of vertices and edges. The next $M$ lines each contain two integers $U_i, V_i$, representing the edge $(U_i, V_i)$. Vertices are labeled $1, 2, \dots, N$.

Output Format

One line with $N$ integers $A(1), A(2), \dots, A(N)$.

4 3
1 2
2 4
4 3

4 4 3 4

Hint

• For $60\%$ of the testdata, $1 \leq N, M \leq 10^3$.
• For $100\%$ of the testdata, $1 \leq N, M \leq 10^5$.

Translated by ChatGPT 5