P3916 Graph Traversal

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)$.

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$.

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

- 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