Sergey's problem
Contest: Codeforces Round 503 (by SIS, Div. 1)
Difficulty rating: 3000
Tags: constructive algorithms, graphs

Sergey just turned five years old! When he was one year old, his parents gave him a number; when he was two years old, his parents gave him an array of integers. On his third birthday he received a string. When he was four, his mother woke him up in a quiet voice, wished him to be a good boy and gave him a rooted tree. Today he celebrates his birthday again! He found a directed graph without loops as a present from his parents.

Since Sergey is a very curious boy, he immediately came up with a thing to do. He decided to find a set $$$Q$$$ of vertices in this graph, such that no two vertices $$$x, y \in Q$$$ are connected by an edge, and it is possible to reach any vertex $$$z \notin Q$$$ from some vertex of $$$Q$$$ in no more than two moves.

After a little thought, Sergey was able to solve this task. Can you solve it too?

A vertex $$$y$$$ is reachable from a vertex $$$x$$$ in at most two moves if either there is a directed edge $$$(x,y)$$$, or there exist two directed edges $$$(x,z)$$$ and $$$(z, y)$$$ for some vertex $$$z$$$.

Input format:
The first line of input contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 1\,000\,000$$$, $$$1 \le m \le 1\,000\,000$$$) — the number of vertices and the number of edges in the directed graph.

Each of the following $$$m$$$ lines describes a corresponding edge. Each one contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) — the beginning and the end of the $$$i$$$-th edge. The graph may contain multiple edges between the same pair of vertices.

Output format:
First print the number $$$k$$$ — the number of selected vertices. Then print $$$k$$$ distinct integers — the indices of the selected vertices.

If multiple answers exist you can output any of them. In particular, you don't have to minimize the number of vertices in the set. It is guaranteed, that there is always at least one valid set.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the vertices $$$1, 3, 4, 5$$$ are not connected. The vertex $$$2$$$ is reachable from vertex $$$1$$$ by one edge.

In the second sample, it is possible to reach the vertex $$$1$$$ in one move and the vertex $$$2$$$ in two moves.

The following pictures illustrate sample tests and their answers.

Example input:
5 4
1 2
2 3
2 4
2 5

Example output:
4
1 3 4 5

Example input:
3 3
1 2
2 3
3 1

Example output:
1
3

Editorial:
Let's build the solution by induction. Suppose we have to solve the problem for $$$n$$$ vertices and we can solve this problem for all $$$k$$$ ($$$k < n$$$). Take an arbitrary vertex $$$A$$$. Remove $$$A$$$ from the graph, as well as all vertices that $$$A$$$ has an outgoing edge to. Resulting graph has less than $$$n$$$ vertices, so by induction, we can build the solution for it. Let's call the answer set for the new graph $$$M$$$. After this we have two cases: either there is an edge from set $$$M$$$ to vertex $$$A$$$ or there is not. If there is an edge from $$$M$$$ to $$$A$$$, then $$$M$$$ is a correct answer for initial graph, because every removed vertex can be reached from $$$M$$$ in at most two steps. Otherwise, we can add $$$A$$$ to $$$M$$$ and, again, this set will satisfy the required condition. This also proves the answer always exists.
How to implement it? Let's iterate over all vertices in order from $$$1$$$ to $$$n$$$ and remember whether each vertex is currently present in the graph or not. Whenever we encounter a currently present vertex $$$u$$$, we save $$$u$$$ and mark $$$u$$$ and all vertices reachable from $$$u$$$ in one step as removed. After that, we go over all saved vertices in reverse order and add them to answer set if it's not reachable from the answer set in one step.
This solutions works in $$$O(V + E)$$$ time and space.