CF2239F.Colorful Works

Gold14526 is a painter. He can paint with $n$ colors, numbered $1, 2, \ldots, n$. Color $i$ has a constraint interval $[l_i, r_i]$.

A work is defined as a rooted tree $T=(V,E)$ where every edge is colored (with one of the $n$ colors). A work is called colorful if the following conditions are satisfied:

• For any three nodes $u, v, w \in V$, if edges $(u,v)$ and $(v,w)$ both exist, they must have different colors.
• For all colors $i \in [1,n]$, let $d(u,i)$ denote the number of edges of color $i$ on the simple path from node $u$ to the root. Then $\max_{u \in V} d(u,i) \in [l_i, r_i]$.

Two works $T=(V,E)$ and $T'=(V',E')$ are defined as isomorphic if and only if the following two conditions are met:

• $\lvert V\rvert = \lvert V'\rvert$;
• There exists a bijection $f:V \to V'$ such that:
  • Let $r$ be the root of $T$ and $r'$ be the root of $T'$. Then $f(r) = r'$;
  • For any $(u,v) \in E$, we have that $(f(u),f(v)) \in E'$, and the color of edge $(u,v)$ is the same as the color of edge $(f(u),f(v))$.

Gold14526 wants to know the maximum number of colorful works he can choose such that the works are pairwise non-isomorphic. Output the answer modulo $\bf2$.

Gold14526 是一位画家。他可用 $n$ 种颜色进行绘画，颜色编号为 $1, 2, \ldots, n$。颜色 $i$ 具有约束区间 $[l_i, r_i]$。

一幅作品定义为一棵有根树 $T=(V,E)$，其中每条边均被染色（使用 $n$ 种颜色之一）。若一幅作品满足以下条件，则称其为多彩的（colorful）：

• 对任意三个节点 $u, v, w \in V$，若边 $(u,v)$ 和 $(v,w)$ 均存在，则它们的颜色必须不同；
• 对所有颜色 $i \in [1,n]$，令 $d(u,i)$ 表示从节点 $u$ 到根节点的简单路径上颜色为 $i$ 的边的数量，则需满足 $\max_{u \in V} d(u,i) \in [l_i, r_i]$。

两幅作品 $T=(V,E)$ 与 $T'=(V',E')$ 被定义为同构的（isomorphic），当且仅当满足以下两个条件：

• $\lvert V\rvert = \lvert V'\rvert$；
• 存在双射 $f:V \to V'$，使得：
  • 设 $r$ 为 $T$ 的根节点，$r'$ 为 $T'$ 的根节点，则 $f(r) = r'$；
  • 对任意 $(u,v) \in E$，均有 $(f(u),f(v)) \in E'$，且边 $(u,v)$ 的颜色与边 $(f(u),f(v))$ 的颜色相同。

Gold14526 想知道：他最多能选出多少幅互不同构的多彩作品？输出答案对 $\bf2$ 取模的结果。

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 an integer $n$ ($1\le n\le 2\cdot 10^6$) — denoting the number of colors.

The following $n$ lines each contain two integers, the $i$ -th of them $l_i$ and $r_i$ ($0\le l_i\le r_i\le 2\cdot 10^5$, $r_i\ge 1$) — denoting the constraint interval of the $i$ -th color.

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

Let $m=\max_{i=1}^n r_i$. Then it is guaranteed that the sum of $m$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^6$），表示颜色种类数。

接下来的 $n$ 行，每行包含两个整数；其中第 $i$ 行为 $l_i$ 和 $r_i$（$0\le l_i\le r_i\le 2\cdot 10^5$，且 $r_i\ge 1$），表示第 $i$ 种颜色的约束区间。

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

令 $m=\max_{i=1}^n r_i$，则保证所有测试用例中 $m$ 的总和不超过 $2\cdot 10^5$。

For each test case, output $0$ or $1$, representing the maximum number of works that can be chosen modulo $2$.

对于每个测试用例，输出 $0$ 或 $1$，表示最多可选择的作品数量对 $2$ 取模的结果。

In the first test case, the constraints for both colors are $[0, 1]$. This means on any simple path from the root, there can be at most $1$ edge of color $1$ and at most $1$ edge of color $2$. There are exactly $9$ valid pairwise non-isomorphic trees:

• $1$ tree with $1$ node: just the root.
• $2$ trees with $2$ nodes: the root is connected to a child by an edge of color $1$, or by an edge of color $2$.
• $3$ trees with $3$ nodes:
  • the root is connected to two children by edges of color $1$ and $2$ respectively.
  • a path of $2$ edges from the root, colored $1$ then $2$.
  • a path of $2$ edges from the root, colored $2$ then $1$.
• $2$ trees with $4$ nodes:
  • the root has a child via color $1$ (which further has a child via color $2$), and another child via color $2$.
  • the root has a child via color $2$ (which further has a child via color $1$), and another child via color $1$.
• $1$ tree with $5$ nodes: the root is connected to two children by colors $1$ and $2$, and each of these children has exactly one child of the opposite color.

Since $9 \equiv 1 \pmod 2$, the output is $1$.

In the second test case, the constraints for both colors are $[1, 1]$. Every valid tree must satisfy the maximum count of each color on the paths to be exactly $1$. Therefore, the tree must contain at least one edge of color $1$ and at least one edge of color $2$. There are exactly $6$ valid trees:

• $3$ trees with $3$ nodes: the root connected to two children by colors $1$ and $2$; a path colored $1$ then $2$; a path colored $2$ then $1$.
• $2$ trees with $4$ nodes: same as the two $4$-node trees described in the first test case.
• $1$ tree with $5$ nodes: same as the $5$-node tree described in the first test case.

Since $6 \equiv 0 \pmod 2$, the output is $0$.

在第一个测试用例中，两种颜色的约束均为 $[0, 1]$。这意味着：在从根节点出发的任意简单路径上，颜色 $1$ 的边至多出现 $1$ 次，颜色 $2$ 的边也至多出现 $1$ 次。恰好存在 $9$ 棵互不同构的有效树：

• $1$ 棵含 $1$ 个节点的树：仅包含根节点。
• $2$ 棵含 $2$ 个节点的树：根节点通过颜色 $1$ 的边连接一个子节点，或通过颜色 $2$ 的边连接一个子节点。
• $3$ 棵含 $3$ 个节点的树：
  • 根节点分别通过颜色 $1$ 和颜色 $2$ 的边连接两个子节点；
  • 从根节点出发的长度为 $2$ 的路径，其边颜色依次为 $1$、$2$；
  • 从根节点出发的长度为 $2$ 的路径，其边颜色依次为 $2$、$1$。
• $2$ 棵含 $4$ 个节点的树：
  • 根节点通过颜色 $1$ 的边连接一个子节点（该子节点再通过颜色 $2$ 的边连接其子节点），同时根节点还通过颜色 $2$ 的边连接另一个子节点；
  • 根节点通过颜色 $2$ 的边连接一个子节点（该子节点再通过颜色 $1$ 的边连接其子节点），同时根节点还通过颜色 $1$ 的边连接另一个子节点。
• $1$ 棵含 $5$ 个节点的树：根节点通过颜色 $1$ 和颜色 $2$ 的边分别连接两个子节点，且这两个子节点各自恰好有一个颜色与父边相反的子节点。

由于 $9 \equiv 1 \pmod 2$，输出为 $1$。

在第二个测试用例中，两种颜色的约束均为 $[1, 1]$。每棵有效树必须满足：从根节点出发的任意路径上，每种颜色的边出现次数恰好为 $1$。因此，该树必须至少包含一条颜色 $1$ 的边和一条颜色 $2$ 的边。恰好存在 $6$ 棵有效树：

• $3$ 棵含 $3$ 个节点的树：根节点通过颜色 $1$ 和颜色 $2$ 的边连接两个子节点；颜色序列为 $1$、$2$ 的长度为 $2$ 的路径；颜色序列为 $2$、$1$ 的长度为 $2$ 的路径。
• $2$ 棵含 $4$ 个节点的树：与第一个测试用例中描述的两棵 $4$ 节点树相同。
• $1$ 棵含 $5$ 个节点的树：与第一个测试用例中描述的 $5$ 节点树相同。

由于 $6 \equiv 0 \pmod 2$，输出为 $0$。