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_25_07 - Wytyczanie działek

Zmiana planu zagospodarowania prestrzennego spowodowała, że burmistrz Bajtogrodu musi wytyczyć nowe działki budowlane. W związku z tym, zakupiono pewną liczbę słupków i dużą ilość siatki ogrodzeniowej oraz wiele innych niezbędnych elementów. Słupki wbito w ziemię w różnych punktach w terenie wyznaczonym do rozparcelowania, a następnie pomiędzy wybranymi parami słupków rozpięto siatkę wyznaczając w ten sposób działki.

Niestety, niechlujstwo pracowników zajmujących się montażem ogrodzenia doprowadziło do sytuacji, w której powstałe działki mają różne pola powierzchni i dość nieregularne kształty, a dodatkowo, nikt nie wie ile tych działek właściwie jest. Wiadomo jedynie, które słupki zostały połączone siatką i że żadne dwa jej fragmenty nie krzyżują się. Burmistrz zlecił Ci napisanie programu, który, na podstawie jedynie tych danych, wyznaczy liczbę nowopowstałych działek.

Wejście

W pierwszej linii liczba testów t (t10).
W pierwszej linii każdego testu dwie liczby całkowite n (0n1000) i m (0m1000) oznaczające odpowiednio liczbę słupków i liczbę par słupków połączonych siatką.
W kolejnych m liniach po dwie liczby całkowite z zakresu od 1 do n, oznaczające numery połączonych słupków.

Wyjście

Liczba wytyczonych działek. 

Przykład

Wejście:
1
6 6
1 2
2 3
3 4
4 5
5 1
2 4 Wyjście: 2

Dodane przez:Witold Długosz
Data dodania:2015-11-05
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY

ukryj komentarze
2015-11-08 09:09:19 Witold D³ugosz
1. Tak.
2. Tak.

Ostatnio edytowany: 2015-11-08 09:11:57
2015-11-07 23:58:44 Kamil Wajda
1. Czy może się zdarzyć, że rozłożone siatki NIE utworzą wielokątu? Innymi słowy, czy poprawnym wejściem jest np. takie:
1
2 1
1 2
?

Jeśli tak to jaka jest w tym przypadku poprawna odpowiedź? 0?

2. Czy można założyć, że każda nieuporządkowana para połączonych siatką słupków pojawi się tylko raz w danym przypadku testowym?

Ostatnio edytowany: 2015-11-08 00:07:41
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.