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.|

FR_10_20 - Teatry

W Bajtlandii urząd króla sprawuje dzielny Bajtomir. Znany ze swojej waleczności na całym kontynencie, poprowadził swój kraj do zwycięstwa w wojnie z Bitlandią. Nastały jednak czasy pokoju i król dla odmiany zadecydował zainwestować pieniądze w kulturę. Postanowił wybudować w wybranych miastach teatry. Ponieważ fundusze ma ograniczone wolałby nie budować teatru w każdym mieście. Aby jednak zminimalizować niezadowolenie mieszkańców wymyślił jak można efektywnie rozplanować ich budowę: niech każde miasto zawiera teatr lub jest w bezpośrednim sąsiedztwie z jakimś miastem zawierającym teatr. Dwa miasta są w bezpośrednim sąsiedztwie jeśli istnieje droga je łącząca.

Jako inżynier króla zaobserwowałeś ciekawą własność sieci dróg Bajtlandii: pomiędzy każdą parą miast istnieje dokładnie jedna ścieżka je łącząca. Teraz pozostaje tylko wyliczenie ile minimalnie teatrów należy zbudować.

Wejście

Wejście rozpoczyna liczba testów 1 ≤ t ≤ 10. Następnie podawane są kolejne testy.

Pojedynczy test rozpoczyna liczba 1 ≤ n ≤ 105 oznaczająca liczbę miast Bajtlandii. W kolejnych n-1 liniach podany jest opis sieci dróg kraju. W każdej linii znajdują się dwie liczby 1 ≤ a, bn; ab oznaczające istnienie bezpośredniego połączenia między miastami a oraz b.

Wyjście

Dla każdego testu wynik należy podać w osobnej linii. Wynikiem jest minimalna liczba teatrów które należy wybudować w miastach Bajtlandii, aby spełnione były wymagania Bajtomira.

Przykład

Wejście:

2
5
1 2
3 1
3 4
5 3
2
1 2

Wyjście:

2
1

Dodane przez:Adam Bąk
Data dodania:2018-12-20
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: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.