← 返回题目列表

Codeforces · 2178/G

G. deCH 或日期

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

由于北极的供应链问题(据称是由懒惰的小精灵造成),圣诞老人计划在今年圣诞节分发手绘圆圈作为礼物。请帮他装饰它们!

圆周围有 $$$2n$$$ 等距点,按顺时针顺序标记为 $$$1,2,\ldots,2n$$$。圣诞老人选择了 $$$n$$$ 和弦 不同 上面写着 端点,其中弦 $$$i$$$ 连接点 $$$a_i$$$ 和 $$$b_i$$$。他将这些和弦按顺序一一画在圆圈上。

圣诞老人画完第一个 $$$\ell$$$ 和弦后,考虑 $$$\ell$$$ 和弦的任何非空子集 $$$S$$$ 并让 $$$1\leq c_1 \lt c_2 \lt \cdots \lt c_{|S|}\leq \ell$$$ 为其索引。 $$$S$$$ 被定义为 链条 当且仅当和弦 $$$c_k$$$ 与所有 $$$1\leq k \lt |S|$$$ 与和弦 $$$c_{k+1}$$$ 相交。请注意,$$$S$$$ 始终是 链条 如果$$$|S|=1$$$。

圣诞老人不希望任何和弦出现异常。因此,他认为和弦是 紧密结合 当且仅当每个和弦出现在偶数个中 链条,接管全部 链条 是第一个 $$$\ell$$$ 和弦的子集。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$\ell$$$,帮助圣诞老人确定他的和弦是否 紧密结合.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 5\cdot 10^5$$$) — 和弦的数量。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1\le a_i \lt b_i\le 2n$$$) — 第 $$$i$$$ 和弦的端点。

保证所有端点都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的字符串 — 如果第一个 $$$\ell$$$ 和弦是,则第 $$$\ell$$$ 个字符应该是 $$$\texttt{1}$$$ 紧密结合 和 $$$\texttt{0}$$$ 否则。

示例

输入
复制

3
3
1 6
2 3
4 5
4
1 7
3 8
4 6
2 5
5
1 6
4 9
2 7
5 10
3 8

输出
复制

000
0100
01111

注意

在第一个测试用例中,没有成对的和弦相交,因此每个和弦都恰好出现在一个 链条 由其自身组成。因此,和弦不是 紧密结合 对于所有$$$\ell$$$。

在第二个测试用例中,下面是绘制第一个 $$$\ell=1,2,3,4$$$ 和弦后的说明和解释。和弦组被表示为一组对应和弦的索引。

说明
插图
链条
  • $$$\{1\}$$$.
出场
  • 和弦 $$$1$$$ 出现在 $$$1$$$ 中 链条.
注释
  • 和弦不是 紧密结合 因为和弦 $$$1$$$ 是奇数个 链条.
  • 回想一下,包含单个和弦的集合始终是 链条.
链条
  • $$$\{1\}$$$、$$$\{1,2\}$$$ 和 $$$\{2\}$$$。
出场
  • 和弦 $$$1$$$ 出现在 $$$2$$$ 中 链条;
  • 和弦 $$$2$$$ 出现在 $$$2$$$ 中 链条.
注释
  • 和弦是 紧密结合 因为每个和弦都出现在偶数个中 链条.
链条
  • $$$\{1\}$$$、$$$\{1,2\}$$$、$$$\{2\}$$$ 和 $$$\{3\}$$$。
出场
  • 和弦 $$$1$$$ 出现在 $$$2$$$ 中 链条;
  • 和弦 $$$2$$$ 出现在 $$$2$$$ 中 链条;
  • 和弦 $$$3$$$ 出现在 $$$1$$$ 中 链条.
注释
  • 和弦不是 紧密结合 因为和弦 $$$3$$$ 是奇数个 链条.
链条
  • $$$\{1\}$$$、$$$\{1,2\}$$$、$$$\{1,2,4\}$$$、$$$\{2\}$$$、$$$\{2,4\}$$$、$$$\{3\}$$$、$$$\{3,4\}$$$ 和$$$\{4\}$$$。
出场
  • 和弦 $$$1$$$ 出现在 $$$3$$$ 中 链条;
  • 和弦 $$$2$$$ 出现在 $$$4$$$ 中 链条;
  • 和弦 $$$3$$$ 出现在 $$$2$$$ 中 链条;
  • 和弦 $$$4$$$ 出现在 $$$4$$$ 中 链条.
注释
  • 和弦不是 紧密结合 因为和弦 $$$1$$$ 是奇数个 链条.
  • 请注意 $$$\{2,3,4\}$$$ 是 不 a 链条 因为和弦 $$$2$$$ 不与和弦 $$$3$$$ 相交。

因此,我们输出$$$\mathtt{0100}$$$。