시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Bajtoland jest miastem szczególnie narażonym na pożary. Znajduje się ono w najcieplejszej części Bajtocji, gdzie temperatury dochodzą często do ponad 60 stopni Celsjusza w nocy, a ogień rozprzestrzenia się niewyobrażalnie szybko! Rada miejska Bajtolandu musi więc niezwłocznie podjąć jakieś kroki. Najnowszy pomysł rozwiązania kryzysu przestawiła firma Zgliszcza Sp. z o.o. Proponuje ona system, który pozwoli na zdalne odcinanie obszarów trawionych ogniem od reszty miasta, tak aby jak najszybciej wytłumić ogień. Twoim zadaniem, jako miejscowego analityka, jest stworzenie raportu na temat przedstawionego rozwiązania. Mając do dyspozycji dane na temat historycznych pożarów w Bajtolandzie, musisz określić, jak wiele domów można by uratować, gdyby obecnie zaprezentowane rozwiązanie było wcześniej dostępne.

Od początku istnienia osady Bajtoland, w celu ograniczenia ewentualnych zniszczeń spowodowanych pożarami, nigdy w bezpośrednim otoczeniu pojedynczego zabudowania nie budowano więcej niż trzech innych domów. Poza tym każdy dom, który sąsiaduje z dokładnie trzema domostwami, został wyposażony w automatyczny system wczesnego wykrywania pożarów, który sprawia, że przy powstaniu pożaru w takim domu od razu kierowana jest tam ekipa strażacka Bajtolandu, która tłumi płomienie we wczesnym stadium i uniemożliwia ich rozprzestrzenienie na sąsiednie zabudowania. Dzięki temu taki dom nie może być zarzewiem ogólnomiejskiego pożaru. Uwaga! Bajtoland posiada jedną jednostkę strażacką, na szczęście jak dotąd pożary wybuchały tylko w jednym domostwie na raz. Twój cel to ocena rozwiązania przedstawionego przez firmę Zgliszcza Sp. z o.o., uwzględniająca te fakty. Na propozycję firmy składa się zastąpienie jednostki naziemnej pojedynczą jednostką powietrzną. Każda taka jednostka przewozi ze sobą nieskończoną grupę strażaków. Pojedynczy strażak nie jest niestety w stanie ugasić pożaru, może jednak ochronić pojedynczy dom przed zajęciem się ogniem. Sama jednostka powietrzna porusza się niesamowicie szybko i czas przelotu pomiędzy kolejnymi domostwami jest praktycznie zerowy, jednak zrzucenie strażaka z pełnym sprzętem trwa godzinę, a jest to czas równy temu, ile potrzeba, żeby ogień rozprzestrzenił się z jednego domu na domy sąsiednie. Innowacyjność tej metody polega na tym, że zamiast gasić płonące już budynki, staramy się ochronić inne, czekając aż ogień samoistnie zaniknie. Mogłoby się wydawać, że metoda jest skazana na porażkę, jednak firma Zgliszcza Sp. z o.o. uważa, że dzięki niej straty są zdecydowanie mniejsze niż przy klasycznym podejściu. Wydawałoby się, że najlepszym rozwiązaniem byłoby umieszczenie w każdym domu jednego strażaka, jednak rozwiązanie to jest zbyt drogie!

입력

W pierwszej linii wejścia znajduje się liczba t (1 ≤ t ≤ 20) określająca liczbę zestawów testowych. W kolejnych liniach znajduje się t zestawów testowych. Każdy zestaw zawiera najpierw dwie liczby n, m (1 ≤ n ≤ 105, 0 ≤ m ≤ 3/2 ∗ n) oznaczające kolejno liczbę domostw w mieście oraz liczbę połączeń pomiędzy budynkami. W kolejnych m liniach następuje opis połączeń. Każde połączenie opisują dwa numery domostw, które ze sobą sąsiadują (jest to relacja symetryczna). W ostatniej linii pojedynczego przypadku testowego wyróżniamy numer domu k (1 ≤ k ≤ n), w którym wybuchł pożar.

출력

Dla każdego testu należy podać w osobnej linii pojedynczą wartość określającą liczbę domostw, które można uchronić przed naruszeniem przez ogień.

예제 입력 1

2
4 4
1 2
2 3
3 4
4 1
1
11 10
1 2
2 3
2 4
4 6
3 5
1 11
11 7
8 11
9 7
10 8
1

예제 출력 1

2
8