Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_18_10 - Dostawca pizzy 3

Bitazarowi, po sukcesach w rozwożeniu pizzy (tu i tu), wreszcie udało się uzbierać wystarczająco dużo pieniędzy na założenie własnej sieci pizzerii. Nie stać go na razie na to, aby w każdym mieście znajdowała się jego restauracja, więc postanowił zoptymalizować nieco proces ich budowania. Wymyślił następujące kryterium: niech każde z N miast Bajtogrodu zawiera jego pizzerię lub znajduje się w bezpośrednim sąsiedztwie z miastem które taką pizzerię posiada. W ten sposób zasięg jego sieci będzie w pewnym sensie bardzo daleki. Pytanie zatem - ile minimalnie restauracji musi zbudować?

Wejście

Nieokreślona ilość zestawów danych. Każdy zestaw danych to para liczb naturalnych:  N ≤ 35M oznaczających kolejno liczbę miast Bajtogrodu oraz liczbę połączeń między nimi. Potem następuje M par liczb  a,b ≤ N opisujących te połączenia. Jedna taka para oznacza, że pomiędzy miastami o numerach a oraz b istnieje połączenie (są w bezpośrednim sąsiedztwie). Wejście kończy para (N,M) = (0,0).

Uwaga: pomiędzy dwoma miastami może istnieć wiele połączeń oraz mogą istnieć drogi zaczynające i kończące się w tym samym mieście (tzn a = b).

Wyjście

Dla każdego testu w oddzielnej linii odpowiedź na postawione w treści zadania pytanie.

Przykład

Wejście:
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

Wyjście: 2


Wyjaśnienie do przykładu:
W tym przypadku z jedną pizzerią nie da się spełnić kryterium Bitazara.
Możemy je jednak spełnić stawiając restauracje na przykład w miastach: 4 oraz 6.

 


Dodane przez:Adam Bąk
Data dodania:2014-08-29
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.