A16820 · deCH OR Dations

题目描述

由于北极的供应链出现了问题（据说是一个懒惰的小精灵惹的祸），圣诞老人计划在今年圣诞节送出手绘的圆形作为礼物。请你帮他装饰这些圆形！ 在圆周上有 $2n$ 个等间距的点，顺时针标记为 $1,2,\ldots,2n$。圣诞老人选择了 $n$ 条端点互不相同的弦，第 $i$ 条弦连接点 $a_i$ 和 $b_i$。他将依次把这些弦绘制到圆上。 当圣诞老人画完前 $\ell$ 条弦后，考虑这 $\ell$ 条弦的任何非空子集 $S$，设 $1\leq c_1<c_2<\cdots<c_{|S|}\leq \ell$ 为其编号。如果对于所有 $1\leq k < |S|$，弦 $c_k$ 与弦 $c_{k+1}$ 都相交，则称 $S$ 为一条“链”。注意，如果 $|S|=1$，则 $S$ 总是一条链。 圣诞老人不希望有哪条弦“格格不入”。因此，只有当每条弦在所有子链中出现偶数次时，才认为这些弦是“紧密联系的”。 对于每个 $\ell = 1$ 到 $n$，请你帮圣诞老人判断这前 $\ell$ 条弦是否紧密联系。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。 每个测试用例的第一行为一个整数 $n$（$2\le n\le 5\cdot 10^5$）——表示弦的数量。 接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$（$1\le a_i<b_i\le 2n$），表示第 $i$ 条弦的两个端点。 保证所有端点均不同。 保证所有测试用例的 $n$ 之和不超过 $5\cdot 10^5$。

对于每个测试用例，输出一个长度为 $n$ 的字符串，第 $\ell$ 个字符为 $\mathtt{1}$ 当且仅当前 $\ell$ 条弦是紧密联系的，否则为 $\mathtt{0}$。

输入 #1

输出 #1

000
0100
01111