Hide

Problem AN
Longest path in a DAG

Given a directed acyclic graph, output one of its longest paths.

Input

The first line contains two integers $V$ ($1 \le V \le 100\, 000$), the number of vertices in the graph, and $E$ ($1 \le E \le 200\, 000$), the number of edges.

Next, $E$ lines follow containing the edges. An edge is given by two integers $1 \le a \neq b \le V$, meaning that the edge points from vertex $a$ to vertex $b$. There may be multiple edges between the same pair of vertices. It is guaranteed that there is no cycle in the graph.

Output

First, output the number of vertices on a longest path. Then, output one line with the numbers of those vertices in the order in which they appear on the path. The first vertex should be the one starting the path, i.e. it should have an outgoing edge to the second vertex you output (if there is one).

Sample Input 1 Sample Output 1
3 2
1 2
1 3
2
1 2
Sample Input 2 Sample Output 2
3 3
1 2
1 3
2 3
3
1 2 3

Please log in to submit a solution to this problem

Log in