Problem Description

Given a directed graph $G$ with $n$ nodes and $m$ edges, the nodes in $G$ are numbered $1,2,\ldots,n$ in order. The $i$-th edge ($1\le i\le m$) goes from node $u_i$ to node $v_i$.

Any node in $G$ with in-degree $0$ can be a valid starting node, and any node with out-degree $0$ can be a valid ending node.

If all possible paths in $G$ from any valid starting node to any valid ending node must pass through node $u$, then $u$ is called a mandatory node. Note that a mandatory node can be a valid starting node or a valid ending node.

Please find the indices of all mandatory nodes in $G$.

For example, in the figure below, the valid starting nodes are node $1$ and node $2$, and the valid ending nodes are node $7$ and node $8$.

(1)            (5)---->(7)
   \           ^  \    ^
    v         /    v  /
    (3)      /     (6)
    ^  \    /         \
   /    v  /           v
(2)---->(4)            (8)

All paths from valid starting nodes to valid ending nodes are:

• $1\to 3\to 4\to 5\to 7$
• $1\to 3\to 4\to 5\to 6\to 7$
• $1\to 3\to 4\to 5\to 6\to 8$
• $2\to 3\to 4\to 5\to 7$
• $2\to 3\to 4\to 5\to 6\to 7$
• $2\to 3\to 4\to 5\to 6\to 8$
• $2\to 4\to 5\to 7$
• $2\to 4\to 5\to 6\to 7$
• $2\to 4\to 5\to 6\to 8$

Therefore, there are two mandatory nodes, with indices $4,5$.

Input Format

The first line contains two positive integers $n,m$, representing the number of nodes and the number of edges in the directed graph $G$.

The next $m$ lines each contain two positive integers $u_i,v_i$, representing a directed edge from node $u_i$ to node $v_i$.

It is guaranteed that $G$ has at least one valid starting node and at least one valid ending node, and that there is at least one path from a valid starting node to a valid ending node. Also, there are no isolated nodes (i.e., nodes whose out-degree and in-degree are both $0$).

Output Format

The first line contains an integer, representing the number of mandatory nodes $k$.

If mandatory nodes exist, then the second line outputs the indices of all mandatory nodes in $G$ in increasing order.

8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 4
5 7

2
4 5

8 9
1 3
2 3
3 4
4 5
5 6
6 7
6 8
2 5
4 7

0

Hint

For $40\%$ of the test points, it is guaranteed that $1\le n\le 100$ and $1\le m\le 200$.

For all test points, it is guaranteed that $1\le n\le 1000$ and $1\le m\le 2000$. It is guaranteed that $G$ has at least one valid starting node and at least one valid ending node, and that there is at least one path from a valid starting node to a valid ending node. Also, there are no isolated nodes (i.e., nodes whose out-degree and in-degree are both $0$).

Translated by ChatGPT 5