Empire#1910
The Empire consists of planets numbered from to . Planet number is the capital of the Empire, where the Emperor's residence is located and the troops are gathered. Uprisings often occur on different planets of the Empire, and they must be suppressed by force immediately.
To allow troops to move quickly, one-way teleports are installed between some planets. There are teleports in total. Using the -th teleport, you can instantly move from planet a_i to planet b_i (a_i \ne b_i; there is no movement in the opposite direction). Thus, an uprising on planet can be suppressed in time if there exists a sequence of planets p_1, \ldots, p_k (k \ge 2) such that p_1 = 1, p_k = x, and for each 1 \le i < k, there is a teleport from planet p_i to planet p_{i+1}. After suppressing the uprising, the troops remain on the planet to maintain order, so there is no need to worry about their return to the capital.
Check whether it is possible, using the existing system of teleports, to suppress the uprising on any planet of the Empire. If so, output . Otherwise, find the minimum number of teleports that must be built so that an uprising on any planet can be immediately suppressed. Each new teleport may be constructed between any two planets.
The first line contains two integers and (2 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5).
Each of the next lines contains two integers a_i and b_i (1 \le a_i, b_i \le n, a_i \ne b_i), representing a teleport from planet a_i to planet b_i. No planet has a teleport to itself. No two teleports go from the same planet to the same destination.
Print the minimum number of teleports needed to ensure that an uprising on any planet can be immediately suppressed.
Example 1