favorite We need a little bit of your help to keep things running, click on this banner to learn more

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 p1, ..., pk (k2) such that p1 = 1, pk = x, and for each 1i < 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 (2n105, 0m2·105). The i-th of the next m lines contains the pair of numbers ai, bi (1ai, bin) for all 1im. 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.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
6 4
3 1
4 6
1 2
4 5
Output example #1

Example description: Its possible to build the teleport from the planet 2 to planet 4 and from the planet 5 to planet 3.

Author Eldar Bogdanov
Source Winter School, Kharkov, 2011, Day 7