15091509 SUSTech Online Judge
Problem 1509 --Simple Graph Problem

1509: Simple Graph Problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 627  Solved: 244
[Submit][Status][Web Board]

Description

Given a directed graph with $$m$$edges, whose nodes are indexed from $$1$$ to $$n$$.
Satori wants to know for each node $$i$$, the maximum index node it can reach.

Input

The first line contains three integers $$n,m(1\le n,m\le 100000)$$, i.e. the number of nodes and the number of edges.
Then $$m$$ lines follow. Each line contains two integers $$u,v(u\ne v,1\le u,v,\le n)$$which means a directed edge from $$u$$ to $$v$$

Output

For each node $$i$$, print an integer with the maximum index of the node it can reach.

6 6
2 6
6 5
3 2
6 3
2 1
4 5

1 6 6 5 5 6

HINT

There is no guarantee that there are no multiple edges and self-loops.

[Submit][Status]