Strong Connected Components
The Empire consists of n planets. Lets label these planets with numbers from 1 to
n. The planet with the number 1 is a capital of Empire, where the Emperor residence is located and the troops are prepared. On different planets of the empire the uprisings are often, which must be suppressed by force and immediately.
In order for troops to move quickly, the one-way teleports are installed on some planets. There are m teleports in total. Using the i-th teleport you can get instantly from planet
ai to planet
bi (but not vice versa). Thus, it is possible to crush the rebellion in time on some planet x, if there is a sequence of planets
pk (k ≥ 2) such that
p1 = 1,
pk = x, and for each 1 ≤ i < k there is a teleport from planet with number
pi to the planet with number
pi+1. After crushing the uprising, the troops remain on the planet to maintain the order, so we do not need to worry about their return to the capital.
Check is there an opportunity using the existing system of teleports to crush the rebellion on any planet of the Empire. If so, print 0. Otherwise find the minimum number of teleports that must be built more so that the rebellion on any planet can be suppressed instantly. Each new teleport can be constructed between any two planets.
The first line contains two integers n and m (2 ≤ n ≤
105, 0 ≤ m ≤ 2·
105). The i-th of the next m lines contains the pair of numbers
bi (1 ≤
bi ≤ n) for all 1 ≤ i ≤ m. No one planet has a teleport to itself. No one planet has two teleports to the same planet.
Print the minimum number of teleports, ensuring that the revolt on any planet can be immediately suppressed.
6 4 3 1 4 6 1 2 4 5
Example description: Its possible to build the teleport from the planet 2 to planet 4 and from the planet 5 to planet 3.