Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Разбиение и объединение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано $$$n$$$ отрезков $$$[l_i, r_i]$$$ для всех $$$1 \le i \le n$$$. Ваша задача — разделить все отрезки на две непустые группы таким образом, чтобы не существовало пары отрезков из разных групп, имеющих хотя бы одну общую точку, или же сказать, что это сделать невозможно. Каждый отрезок должен принадлежать ровно одной из групп.

Чтобы оптимизировать процесс тестирования, будет дан мультитест.

Входные данные

Первая строка входных данных содержит одно целое число $$$T$$$ ($$$1 \le T \le 50000$$$) — количество запросов. Каждый запрос содержит описание набора отрезков. Запросы независимы друг от друга.

Первая строка каждого запроса содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество отрезков. $$$\sum{n}$$$ по всем запросам не превосходит $$$10^5$$$.

Следующие $$$n$$$ строк содержат по два целых числа $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — $$$i$$$-й отрезок.

Выходные данные

Для каждого запроса выведите $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$t_i \in \{1, 2\}$$$) — для каждого отрезка (в том же порядке, что и во входных данных) $$$t_i$$$ равно $$$1$$$, если $$$i$$$-й отрезок принадлежит первой группе, или же $$$2$$$ иначе.

Если существует несколько возможных ответов, вы можете вывести любой из них. Если ответа не существует, выведите $$$-1$$$.

Пример
Входные данные
3
2
5 5
2 3
3
3 5
2 3
2 3
3
3 3
4 4
5 5
Выходные данные
2 1 
-1
1 1 2
Примечание

В первом запросе первый и второй отрезки должны быть в разных группах, но точный порядок чисел не важен.

Во втором запросе третий отрезок пересекается с первым и вторым отрезками, таким образом они должны находиться в одной группе, но другая группа при этом окажется пустой, поэтому ответ равен $$$-1$$$.

В третьем запросе мы можем распределить отрезки любым образом, которые делает группы непустыми, так что любой ответ из $$$6$$$ возможных подходит.