NPC2015C - Eefun Plays Doto

Doto is a famous game. In that game, each player controls N heroes where each heroes has an infinite number of skills. These skills can be used to empower other heroes. Eefun is currently playing with his N heroes, numbered from 1 to N.

The main objective of this game is to defeat the enemies with these heroes. However, Eefun always lose the game, so now Eefun only try to make his heroes powerful.

Based on Eefun's logic, there are M requirements to make all of his heroes powerful. Each requirement needs a hero A and a hero B. Hero A must use his/her skill to hero B to make B more powerful. Moreover, if hero B and C needs skill from hero A, hero A can use his/her skill to hero B. Then, hero B skills will be empowered with skills from hero A. Therefore, he can use his skill to hero C. In this scenario, the number of skills activated is 2, where A doesn't get any skills, B get skill from hero A, and C get skill from both hero A and B.

The skill is continuous, so if A give his skill to B, B give his skill to C, and C give his skill to A, then every hero get every other heroes skills

Now Eefun is curious, how many skills must be activated to complete all his requirements 

Input

First line consists of 2 integers, N and M which denotes number of heroes and requirements.
Next M skills each contains 2 integers, A and B, which means hero B will be powerful if he get skills from hero A. 

Output

Output an integer, the minimum number of skills which must be activated to complete all the requirements

Example

Input 1:
3 4
1 2
2 3
3 1
2 1

Output 1:
3
Input 2:
5 5
1 5
3 4
4 3
2 5
1 3

Output 2:
5

Explanation

  • For the first case, hero 1 can give his skill to hero 2, hero 2 can give his skill to hero 3, and hero 3 can give his skill to hero 1.
  • For the second case, one of the configuration is like in the picture below :
     

Constraints:

  • A ≠ B
  • 1 ≤ A,B ≤ N
  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 100.000

Added by:Louis Arianto
Date:2015-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:NPC Schematics 2015

hide comments
2018-09-19 14:10:27
uhm, where is the picture for the second testcase's explanation?
[Simes]: Eventually restored

Last edit: 2023-06-15 10:13:21
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.