Gold14526 是一名画家。他可以用$$$n$$$颜色进行绘画,编号为$$$1、2、\ldots、n$$$。颜色 $$$i$$$ 有一个约束区间 $$$[l_i, r_i]$$$。
作品被定义为 有根树 $$$T=(V,E)$$$,其中每条边都有颜色(使用 $$$n$$$ 颜色之一)。有一个作品叫做 多彩 如果满足以下条件:
- 对于任意三个节点 $$$u, v, w \in V$$$,如果边 $$$(u,v)$$$ 和 $$$(v,w)$$$ 都存在,则它们必须具有不同的颜色。
- 对于 [1,n]$$$ 中的所有颜色 $$$i,让 $$$d(u,i)$$$ 表示从节点 $$$u$$$ 到根的简单路径上颜色 $$$i$$$ 的边数。然后$$$\max_{u \in V} d(u,i) \in [l_i, r_i]$$$。
当且仅当满足以下两个条件时,两个作品 $$$T=(V,E)$$$ 和 $$$T'=(V',E')$$$ 被定义为同构:
- $$$\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$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 $$$0$$$ 或 $$$1$$$,表示可以选择的最大作品数对 $$$2$$$ 取模。
示例
输入复制
420 10 121 11 130 20 10 131 21 11 1
输出复制
1011
注意
在第一个测试用例中,两种颜色的约束都是 $$$[0, 1]$$$。这意味着在从根开始的任何简单路径上,最多可以有 $$$1$$$ 颜色为 $$$1$$$ 的边缘,最多有 $$$1$$$ 颜色为 $$$2$$$ 的边缘。总共有 $$$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$$$ 连接到两个子节点,并且每个子节点都有一个相反颜色的子节点。
在第二个测试用例中,两种颜色的约束均为 $$$[1, 1]$$$。每棵有效的树必须满足路径上每种颜色的最大计数恰好为 $$$1$$$。因此,树必须至少包含一条颜色为 $$$1$$$ 的边和至少一条颜色为 $$$2$$$ 的边。总共有 $$$6$$$ 有效树:
- $$$3$$$ 树,具有 $$$3$$$ 节点:根通过颜色 $$$1$$$ 和 $$$2$$$ 连接到两个子节点;路径颜色为$$$1$$$,然后是$$$2$$$;路径颜色为$$$2$$$,然后是$$$1$$$。
- 具有 $$$4$$$ 节点的 $$$2$$$ 树:与第一个测试用例中描述的两个 $$$4$$$ 节点树相同。
- 具有 $$$5$$$ 节点的 $$$1$$$ 树:与第一个测试用例中描述的 $$$5$$$ 节点树相同。