Atlas

Treść

Członkowie Koła Naukowego Wydziału Informatyki po wielu sukcesach w międzynarodowych konkursach programistycznych nie spoczywają na laurach i przygotowują się do następnych. Tym razem postanowili zrealizować multimedialny interaktywny atlas świata. Oprócz wielu innowacji, takich jak prognozowanie wędrówki kontynentów czy symulacja efektu motyla, oprogramowanie będzie zawierać wszystkie charakterystyczne dla tego typu projektów funkcjonalności.

Jedną z nich jest polityczna mapa świata. Aby móc ją poprawnie wygenerować nasi programiści potrzebują informacji o sąsiedztwie poszczególnych państw. Możesz im pomóc pisząc moduł, który będzie podawał takie informacje. Dla zbioru państw opisanych jako wielokąty wyznacz liczbę sąsiadów każdego z nich. Dla ułatwienia pisania pierwszej wersji możesz przyjąć, że na mapie nie występują enklawy, a każdy z krajów jest podany jako pojedynczy wielokąt.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

W pierwszym wierszu zestawu danych znajduje się liczba państw n (1<=n<=10000). Dalej podane są opisy poszczególnych państw.

Pierwszy wiersz takiego opisu zawiera liczbę wierzchołków m_i (3<=m_i<=100000) opisujących granicę i-tego państwa. W kolejnych m_i wierszach znajdują się po dwie liczby całkowite x_j i y_j (0<=x_j,y_j<=10⁹), oddzielone pojedynczą spacją, definiujące położenie j-tego wierzchołka w kartezjańskim układzie współrzędnych. Po połączeniu kolejnych wierzchołków, oraz ostatniego z pierwszym, otrzymamy nieprzecinające się odcinki definiujące granicę i-tego państwa.

Można założyć, że dane wejściowe zawsze reprezentują poprawną mapę, a sumaryczna liczba wierzchołków nie przekracza 100000. Oprócz tego żadna para odcinków nie pokrywa się częściowo. Dowolne dwa odcinki mogą być całkowicie rozłączne, stykać się w jednym z końców lub całkowicie się pokrywać.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest ciąg liczb całkowitych oznaczających liczbę sąsiadów kolejnych państw podanych na wejściu. Każdy element tego ciągu powinien być wypisany w osobnym wierszu. Należy przyjąć, że dwa państwa sąsiadują ze sobą wtedy i tylko wtedy, gdy istnieje co najmniej jeden wspólny odcinek ich granic.

Przykład

dane wejściowe:
1
4
4
0 2
2 2
2 4
0 4
3
2 4
0 4
1 5
3
0 2
2 2
1 1
3
2 2
4 2
3 1

wynik:
2
1
1
0