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 $ .

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 $ .

For each test case, output $ 0 $ or $ 1 $ , representing the maximum number of works that can be chosen modulo $ 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 $ .