Due to recent unfortunate accidents in the airways, airport control authority have decided that there will be separate paths/airways for going and coming back for airplanes from one airport to another. As like, suppose there are two airports A and B then for going from A to B and coming from B to A, there are two separate paths . For the sake of convenience, airport's authority have decided that if there is any direct or indirect path from some airport to other airport, a passenger needs to go through security check only once. For example there is a path from airport A to B , from B to C , from C to D , then a person travelling from A to D , needs to go through security check only once . If there are in total N airports, you have to find the minimum number of security checks needed to travel to all airports at least once .
First line of input contains N and M, where N is the total number of airports and M is the number of paths from some arbitrary airport X to Y. Next M lines contains two integers X and Y , where there is a path from X to Y .
The only line of output should contain the minimum number of security checks needed to travel all airports atleast once.
Constraints and subtasks
- 1 ≤ N ≤ 105
- 0 ≤ M ≤ 5 * 105
- 1 ≤ X, Y ≤ N Sub-task 1: 5 points
- 1 ≤ N ≤ 105
- M= 0 Sub-task 2: 95 points
- Original constraints
Input: 3 3 1 2 2 1 2 3 Output: 1
Example case 1. A person going through security check at either airport 1 or 2 can visit all the airports.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions