Вы — большая рыба, и однажды вы плаваете в море.
Море можно представить как координатную плоскость, на которой расположено $n$ островов. $i$-й остров имеет координаты $\left( x_i, y_i \right)$, и на нем проживает $i$ человек.
Вам нравится плавать вдоль направлений, параллельных осям $x$ или $y$. Маршрут плавания считается «счастливым», если он удовлетворяет следующим условиям:
- Маршрут параллелен оси $x$ и проходит от $-\infty$ до $+\infty$ по координате $y$, либо маршрут параллелен оси $y$ и проходит от $-\infty$ до $+\infty$ по координате $x$.
- Вдоль направления вашего движения вы проходите хотя бы через один остров.
- Наибольший общий делитель (НОД) количества людей на всех островах, встреченных на пути, равен $1$.
(ps: В частности, НОД одного числа равен самому этому числу)
Вы хотите, чтобы количество счастливых маршрутов было как можно больше, поэтому вы обратились к богине воды с просьбой помочь вам контролировать эту акваторию для достижения вашей цели.
К сожалению, богиня воды не может изменить координаты островов, она может лишь перераспределить количество людей на каждом острове так, чтобы оно представляло собой перестановку чисел от $1$ до $n$.
Однако богиня воды не очень сильна в вычислениях, поэтому ей нужно, чтобы вы предложили план, по которому она перераспределит количество людей на этих $n$ островах.
Ваша задача: найти такой план распределения людей, чтобы количество счастливых маршрутов было максимально возможным при соблюдении условий богини.
Входные данные
Задача содержит несколько наборов входных данных.
Первая строка содержит целое положительное число $T$, количество наборов данных.
Для каждого набора данных первая строка содержит целое положительное число $n$, количество островов.
Далее следуют $n$ строк, каждая из которых содержит два целых положительных числа $x_i, y_i$, координаты острова. Гарантируется, что координаты всех островов различны.
Выходные данные
Для каждого набора данных выведите две строки:
В первой строке выведите целое число — максимально возможное количество счастливых маршрутов.
Во второй строке выведите $n$ целых чисел, представляющих количество людей на каждом острове в порядке, соответствующем входным данным. Вы должны гарантировать, что выведенные $n$ чисел являются перестановкой чисел от $1$ до $n$.
Если существует несколько решений, можно вывести любое из них.
Примечание: Если для всех наборов данных вы правильно выведете значение в первой строке, вы получите $\color{red}{25 \%}$ баллов за подзадачу. Однако, даже если вы претендуете только на эту часть баллов, вы все равно должны вывести во второй строке перестановку (независимо от того, соответствует ли она вашему ответу).
Примеры
Пример 1
2 4 1 1 1 2 2 1 2 2 5 1 1 2 2 4 4 8 8 16 16
Пример 1 (Выходные данные)
4 1 2 4 3 2 1 2 3 4 5
Примечание к примеру 1
Для первого набора данных:
Существует четыре счастливых маршрута: $x = 1$ (количество людей на островах: $1, 2$), $x = 2$ (количество людей: $4, 3$), $y = 1$ (количество людей: $1, 4$), $y = 2$ (количество людей: $2, 3$).
Для второго набора данных:
Существует два счастливых маршрута: $x = 1$ (количество людей: $1$), $y = 1$ (количество людей: $1$).
Пример 2
См. файлы в архиве с условием.
Подзадачи
Для всех тестов выполняются условия: $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$. Для $i \neq j$ гарантируется $x_i \neq x_j \vee y_i \neq y_j$.
Размеры данных для подзадач приведены в таблице ниже:
| Подзадача | Баллы | $n$ | $T$ | $x_i,y_i$ | Другие свойства |
|---|---|---|---|---|---|
| $1$ | $4$ | $\le 9$ | $\le 6$ | $\le n$ | Нет |
| $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$ | Нет |
| $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$ | Все острова образуют $4$-связную компоненту |
| $9$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Все острова образуют $4$-связную компоненту |
| $10$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | Количество островов на каждой прямой не равно $2$ |
| $11$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Количество островов на каждой прямой не равно $2$ |
| $12$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | Количество островов на каждой прямой равно $0$ или $2$ |
| $13$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Количество островов на каждой прямой равно $0$ или $2$ |
| $14$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10000$ | Координаты островов распределены равномерно |
| $15$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10000$ | Координаты островов распределены равномерно |
| $16$ | $8$ | $\le 2\times 10^5$ | $=1$ | $\le 10^9$ | Нет |
| $17$ | $4$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $\le 10^9$ | Нет |
Примечание: две целочисленные точки $A, B$ являются $4$-связными тогда и только тогда, когда существует последовательность целочисленных точек $P_0 = A, P_1, P_2, \cdots, P_{m-1}, P_m = B$, такая что $\left| P_i P_{i+1} \right| = 1$ ($0 \leq i < m$).
Примечание: Если для всех наборов данных вы правильно выведете значение в первой строке, вы получите $\color{red}{25 \%}$ баллов за подзадачу. Однако, даже если вы претендуете только на эту часть баллов, вы все равно должны вывести во второй строке перестановку (независимо от того, соответствует ли она вашему ответу). (Важно, поэтому повторяем дважды)
Кроме того, для вашего удобства в файлах к задаче предоставлен checker.cpp. Пожалуйста, скомпилируйте и используйте его самостоятельно; методы использования и заголовочные файлы соответствуют стандарту testlib.