CF2178G deCH OR Dations

由于北极的供应链出现了问题（据说是一个懒惰的小精灵惹的祸），圣诞老人计划在今年圣诞节送出手绘的圆形作为礼物。请你帮他装饰这些圆形！ 在圆周上有 $2n$ 个等间距的点，顺时针标记为 $1,2,\ldots,2n$。圣诞老人选择了 $n$ 条端点互不相同的弦，第 $i$ 条弦连接点 $a_i$ 和 $b_i$。他将依次把这些弦绘制到圆上。 当圣诞老人画完前 $\ell$ 条弦后，考虑这 $\ell$ 条弦的任何非空子集 $S$，设 $1\leq c_1

每组测试数据包含多个测试用例。第一行包含一个整数 $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

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

在第一个测试用例中，没有任意两条弦相交，因此每条弦都只会出现在唯一一条以自身为链的链中。因此对于所有 $\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\}$ 并不是链，因为弦 $2$ 与弦 $3$ 不相交。  所以应该输出 $\mathtt{0100}$。 由 ChatGPT 5 翻译