SUBMERGE - Submerging Islands


Vice City is built over a group of islands, with bridges connecting them. As anyone in Vice City knows, the biggest fear of vice-citiers is that some day the islands will submerge. The big problem with this is that once the islands submerge, some of the other islands could get disconnected. You have been hired by the mayor of Vice city to tell him how many islands, when submerged, will disconnect parts of Vice City. You should know that initially all the islands of the city are connected.

Input

The input will consist of a series of test cases. Each test case will start with the number N (1 ≤ N ≤ 10^4) of islands, and the number M of bridges (1 ≤ M ≤ 10^5). Following there will be M lines each describing a bridge. Each of these M lines will contain two integers Ui, Vi (1 ≤ Ui,Vi ≤ N), indicating that there is a bridge connecting islands Ui and Vi. The input ends with a case where N = M = 0.

Output

For each case on the input you must print a line indicating the number of islands that, when submerged, will disconnect parts of the city.

Example

Input:
3 3
1 2
2 3
1 3
6 8
1 3
6 1
6 3
4 1
6 4
5 2
3 2
3 5
0 0


Output:
0
1

hide comments
sharif ullah: 2017-11-23 08:49:24

this is straightforward AP problem,,,,if u getting WA ,then u just focus on ur implementation,,,,,
i got wa because
1.while calling DFS i just check condition and then increase counter of find ing AP,,,but i think this is wrong for my implementation,,,,cz,,,a node may count twice\
so,,,i just mark AP node in bolean array then, count AP.

Last edit: 2017-11-23 08:49:51
amulyagaur: 2017-10-30 06:32:48

Direct AP

spojabhi: 2017-10-19 21:59:45

@smso
I was also getting ans 3 in same test case but my code was accepted.
I think ans of toolkit was wrong.

smso: 2017-08-24 19:56:08

I tried to find the articulation points and was able to pass most of the test cases in spojtoolkit except the biggest one with N=10000 and M=3000 (answer=1222, mine=4).

Any hints?

namitp: 2017-07-16 09:21:53

Easy One...

updown: 2017-05-31 22:28:37

I was getting WA but I used this test to debug my code. Here is a test case
Input:
5 5
1 2
1 5
2 5
5 3
3 4
4 3
4 1
1 2
2 3
7 8
7 2
7 1
1 2
1 6
1 4
1 3
3 5
4 5
0 0

Output:
2
2
1

kira28: 2017-04-10 12:15:59

This is a classical problem .
Java users must be getting NZEC due to StackOverflowError as the java runtime stack size (by default) is very small.
You will have to increase the stack size by using the constructor of java.lang.Thread :)

Last edit: 2017-04-10 12:16:40
anurag_tangri: 2017-04-06 22:23:08

easy problem. learnt Tarjans algorithm :)

Last edit: 2017-04-06 22:23:37
flyingduchman_: 2017-02-27 19:09:26

Learn to find Articulation Points (or Cut Vertices) in a Graph from geeksforgeeks and a tutorial video** first or get yourself submerged

Last edit: 2017-02-27 19:10:31
vengatesh15: 2017-02-20 16:19:51

easy one in graph :-)


Added by:Hector Navarro
Date:2013-05-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MiniMaraton 2013 - UCV