Jesteś Wielką Rybą, która pewnego dnia pływa w morzu.
Morze można postrzegać jako płaszczyznę współrzędnych, na której znajduje się $n$ wysp. $i$-ta wyspa ma współrzędne $\left( x_i, y_i \right)$ i mieszka na niej $i$ osób.
Lubisz pływać wzdłuż kierunków równoległych do osi $x$ lub osi $y$. Uważasz trasę pływania za szczęśliwą, jeśli spełnia ona następujące warunki:
- Trasa jest równoległa do osi $x$ i biegnie od $-\infty$ do $+\infty$ wzdłuż współrzędnej $y$; lub trasa jest równoległa do osi $y$ i biegnie od $-\infty$ do $+\infty$ wzdłuż współrzędnej $x$.
- Wzdłuż kierunku pływania mijasz co najmniej jedną wyspę.
- Największy wspólny dzielnik (NWD) liczby mieszkańców wszystkich wysp napotkanych na trasie wynosi $1$.
(ps: W szczególności, największy wspólny dzielnik jednej liczby jest równy jej samej)
Chcesz mieć jak najwięcej szczęśliwych tras pływania, więc zwracasz się do bóstwa wody z prośbą o pomoc w kontrolowaniu tego obszaru morza, aby osiągnąć swój cel.
Niestety, bóstwo wody nie może zmienić współrzędnych wysp, może jedynie dostosować liczbę mieszkańców każdej wyspy, przy czym musi zachować warunek, że liczby mieszkańców $n$ wysp stanowią permutację liczb od $1$ do $n$.
Jednak bóstwo wody nie jest zbyt dobre w obliczeniach, więc potrzebuje, abyś przedstawił plan, według którego przydzieli ona na nowo liczbę mieszkańców $n$ wysp.
Twoim zadaniem jest: znaleźć taki plan dostosowania liczby mieszkańców wysp, aby przy zachowaniu warunków bóstwa wody, liczba szczęśliwych tras pływania była jak największa.
Wejście
Zadanie zawiera wiele zestawów danych.
Pierwsza linia zawiera liczbę całkowitą dodatnią $T$, oznaczającą liczbę zestawów danych.
Dla każdego zestawu danych, pierwsza linia zawiera liczbę całkowitą dodatnią $n$, oznaczającą liczbę wysp.
Następnie $n$ linii, każda zawiera dwie liczby całkowite dodatnie $x_i, y_i$, oznaczające współrzędne wyspy. Gwarantuje się, że współrzędne wszystkich wysp są parami różne.
Wyjście
Dla każdego zestawu danych wypisz dwie linie:
Pierwsza linia zawiera liczbę całkowitą, oznaczającą maksymalną możliwą liczbę szczęśliwych tras pływania.
Druga linia zawiera $n$ liczb całkowitych, oznaczających liczbę mieszkańców każdej wyspy, w kolejności zgodnej z wejściem. Musisz zapewnić, że wypisane $n$ liczb stanowi permutację liczb od $1$ do $n$.
Jeśli istnieje wiele rozwiązań, możesz wypisać dowolne z nich.
Uwaga: Jeśli dla wszystkich zestawów danych poprawnie wypiszesz pierwszą linię, otrzymasz $\color{red}{25 \%}$ punktów za to podzadanie. Jednak nawet jeśli chcesz tylko te punkty, musisz w drugiej linii wypisać dowolną permutację (nie musi ona spełniać Twojej odpowiedzi).
Przykład
Przykład 1
2 4 1 1 1 2 2 1 2 2 5 1 1 2 2 4 4 8 8 16 16
Wyjście 1
4 1 2 4 3 2 1 2 3 4 5
Uwagi
Dla pierwszego zestawu danych:
Istnieją cztery szczęśliwe trasy: $x = 1$ (liczba mieszkańców wysp na trasie to $1, 2$), $x = 2$ (liczba mieszkańców to $4, 3$), $y = 1$ (liczba mieszkańców to $1, 4$), $y = 2$ (liczba mieszkańców to $2, 3$).
Dla drugiego zestawu danych:
Istnieją dwie szczęśliwe trasy: $x = 1$ (liczba mieszkańców to $1$), $y = 1$ (liczba mieszkańców to $1$).
Przykład 2
Zobacz załączone pliki.
Podzadania
Dla wszystkich testów spełnione są warunki: $1 \leq T, n \leq 2 \times 10^5; \sum n \leq 2 \times 10^5; 1 \leq x_i, y_i \leq 10^9$. Dla $i \neq j$ gwarantuje się, że $x_i \neq x_j \vee y_i \neq y_j$.
Szczegółowe ograniczenia podzadań przedstawiono w poniższej tabeli:
| Podzadanie | Punkty | $n$ | $T$ | $x_i,y_i$ | Inne właściwości |
|---|---|---|---|---|---|
| $1$ | $4$ | $\le 9$ | $\le 6$ | $\le n$ | brak |
| $2$ | $4 $ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $x_i = y_i$ |
| $3$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $y_i = 1$ |
| $4$ | $4 $ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | $y_i\le 2$ |
| $5$ | $8$ | $\le 9$ | $\le 2\times 10^5$ | $\le n$ | brak |
| $6$ | $8 $ | $\le 50$ | $\le 50 $ | $\le 10^9$ | $\sum n\le 2500$ |
| $7$ | $8$ | $\le 2500$ | $\le 2500 $ | $\le 10^9$ | $\sum n\le 2500$ |
| $8$ | $8 $ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | Wszystkie wyspy tworzą jeden spójny komponent 4-kierunkowy |
| $9$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Wszystkie wyspy tworzą jeden spójny komponent 4-kierunkowy |
| $10$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | Liczba wysp na każdej prostej równoległej do osi nie jest równa $2$ |
| $11$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Liczba wysp na każdej prostej równoległej do osi nie jest równa $2$ |
| $12$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | Liczba wysp na każdej prostej równoległej do osi wynosi $0$ lub $2$ |
| $13$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Liczba wysp na każdej prostej równoległej do osi wynosi $0$ lub $2$ |
| $14$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10000$ | Współrzędne wszystkich wysp są losowane jednostajnie |
| $15$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10000$ | Współrzędne wszystkich wysp są losowane jednostajnie |
| $16$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | brak |
| $17$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | brak |
Uwaga: Dwa punkty kratowe $A, B$ są 4-połączone wtedy i tylko wtedy, gdy istnieje ciąg punktów kratowych $P_0 = A, P_1, P_2, \cdots, P_{m-1}, P_m = B$, taki że $\left| P_i P_{i+1} \right| = 1$ ($0 \leq i < m$).
Uwaga: Jeśli dla wszystkich zestawów danych poprawnie wypiszesz pierwszą linię, otrzymasz $\color{red}{25 \%}$ punktów za to podzadanie. Jednak nawet jeśli chcesz tylko te punkty, musisz w drugiej linii wypisać dowolną permutację (nie musi ona spełniać Twojej odpowiedzi). (To ważne, więc powtarzamy)
Ponadto, dla dobra zawodników, w załączonych plikach przygotowaliśmy checker.cpp. Prosimy o samodzielną kompilację i użycie; sposób użycia oraz nagłówki są zgodne ze standardem testlib.