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
prem134: 2021-08-11 18:14:04

visit codeNcode playlist for graph

ritikgupta: 2021-06-08 21:58:40

codencode brought me here

jeaf_dean: 2021-06-02 17:08:28

how it's a scc problem?

glaucoacassioc: 2020-11-19 18:22:01

fetus thank you bro!

Last edit: 2020-11-19 18:22:13
prashant1199: 2020-11-19 08:59:19

lol CodeNCode brought me here.

mt6170078: 2020-11-18 10:38:42

Don't increment a counter for no of articulattion points because for a same articulation point there may exist it's multiple neighbours having lowlink value at least equal to it's discovery time!!

gauden_199: 2020-11-15 14:16:36

Raise your hand if you came here after watching codeNcode tutorial for this one

pankaj_m05: 2020-10-29 08:20:40

How can this be solved using strongly connected components?

sabbir0152: 2020-09-19 09:09:28

The problem is articulation point ...easy for them know it

krishna_14: 2020-08-26 15:26:50

Don't forget to clear your articulation points set after every test case :)


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