CF2178G.deCH OR Dations

Due to supply chain issues in the North Pole (allegedly caused by a lazy elf), Santa is planning to give out hand-drawn circles as presents this Christmas. Please help him decorate them!

There are $2n$ equally spaced points around the circle, labeled $1,2,\ldots,2n$ in clockwise order. Santa has chosen $n$ chords with distinct endpoints, where chord $i$ connects the points $a_i$ and $b_i$. He draws these chords onto the circle one by one, in order.

After Santa has drawn the first $\ell$ chords, consider any non-empty subset $S$ of the $\ell$ chords and let $1\leq c_1 \lt c_2 \lt \cdots \lt c_{|S|}\leq \ell$ be their indices. $S$ is defined to be a chain if and only if chord $c_k$ intersects chord $c_{k+1}$ for all $1\leq k \lt |S|$. Note that $S$ is always a chain if $|S|=1$.

Santa does not want any chord to be the odd one out. Therefore, he considers the chords to be tight-knit if and only if every chord appears in an even number of chains, taken over all chains that are subsets of the first $\ell$ chords.

For each $\ell$ from $1$ to $n$, help Santa determine whether his chords are tight-knit.

由于北极地区供应链出现问题（据称是由一名懒惰的精灵引起的），圣诞老人今年圣诞节计划发放手绘的圆作为礼物。请帮助他装饰这些圆！

圆周上均匀分布着 $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$。当且仅当对所有 $1\leq k \lt |S|$，弦 $c_k$ 与弦 $c_{k+1}$ 相交时，$S$ 被定义为一条链。注意：若 $|S|=1$，则 $S$ 恒为一条链。

圣诞老人不希望任何一条弦成为“局外者”。因此，他将前 $\ell$ 条弦称为紧密关联的（tight-knit），当且仅当每条弦在所有由前 $\ell$ 条弦构成的链（即所有这些链的集合）中出现的次数均为偶数。

对每个从 $1$ 到 $n$ 的 $\ell$，请帮助圣诞老人判断此时画出的弦是否是紧密关联的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 5\cdot 10^5$) — the number of chords.

Then $n$ lines follow, the $i$-th line containing two integers $a_i$ and $b_i$ ($1\le a_i \lt b_i\le 2n$) — the endpoints of the $i$-th chord.

It is guaranteed that all endpoints are distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

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

For each test case, output a string of length $n$ — the $\ell$-th character should be $\texttt{1}$ if the first $\ell$ chords are tight-knit and $\texttt{0}$ otherwise.

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

In the first test case, no pairs of chords intersect, and thus every chord appears in exactly one chain consisting of itself. Therefore, the chords are not tight-knit for all $\ell$.

In the second test case, below is an illustration and explanation after the first $\ell=1,2,3,4$ chords are drawn. Sets of chords are denoted as a set of the indices of the corresponding chords.

Explanation

Illustration

Chains

• ${1}$.

Appearances

• Chord $1$ appears in $1$ chain.

Notes

• The chords are not tight-knit since chord $1$ is in an odd number of chains.
• Recall that a set containing a single chord is always a chain.

Chains

• ${1}$, ${1,2}$, and ${2}$.

Appearances

• Chord $1$ appears in $2$ chains;
• Chord $2$ appears in $2$ chains.

Notes

• The chords are tight-knit since every chord appears in an even number of chains.

Chains

• ${1}$, ${1,2}$, ${2}$, and ${3}$.

Appearances

• Chord $1$ appears in $2$ chains;
• Chord $2$ appears in $2$ chains;
• Chord $3$ appears in $1$ chain.

Notes

• The chords are not tight-knit since chord $3$ is in an odd number of chains.

Chains

• ${1}$, ${1,2}$, ${1,2,4}$, ${2}$, ${2,4}$, ${3}$, ${3,4}$, and ${4}$.

Appearances

• Chord $1$ appears in $3$ chains;
• Chord $2$ appears in $4$ chains;
• Chord $3$ appears in $2$ chains;
• Chord $4$ appears in $4$ chains.

Notes

• The chords are not tight-knit since chord $1$ is in an odd number of chains.
• Note that ${2,3,4}$ is not a chain since chord $2$ does not intersect chord $3$.

Thus, we output $\mathtt{0100}$.

在第一个测试用例中，没有任何两条弦相交，因此每条弦都恰好出现在仅包含它自身的链中。因此，对于所有 $\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}$。