← 返回题目列表

Codeforces · 1101/C

C. 分裂与联合

中文机器翻译题面 查看原题

$$$1 \le i \le n$$$ 有 $$$n$$$ 段 $$$[l_i, r_i]$$$。您应该将所有线段分为两个非空组,使得来自不同组的线段不存在至少有一个共同点的一对,或者说这是不可能做到的。每个段应该恰好属于一个组。

为了优化测试过程,您将获得多重测试。

输入

第一行包含一个整数 $$$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\}$$$) — 对于每个段(与输入中的顺序相同)如果第 $$$i$$$ 段属于第一个段,则 $$$t_i$$$ 等于 $$$1$$$组和 $$$2$$$ 否则。

如果有多个答案,您可以打印其中任何一个。如果没有答案,则打印$$$-1$$$。

示例

输入 #1

3
2
5 5
2 3
3
3 5
2 3
2 3
3
3 3
4 4
5 5

输出 #1

2 1 
-1
1 1 2

注意

在第一个查询中,第一个和第二个段应该位于不同的组中,但确切的数字并不重要。

在第二个查询中,第三个线段与第一个和第二个线段相交,因此它们应该在同一组中,但随后另一组变为空,所以答案是 $$$-1$$$。

在第三个查询中,我们可以以任何使组非空的方式分配段,因此任何 $$$6$$$ 可能的答案都是正确的。