彩色作品

英文题名：F. Colorful Works
来源：Codeforces 2239F
比赛：Codeforces Round 1105 (Div. 1)
时间限制：5 seconds
空间限制：256 megabytes

题目描述

作品是一棵有根树，边有颜色。要求相邻两条边颜色不同，且每种颜色在任意根到点路径上的最大出现次数落在给定区间 $[l_i,r_i]$。求两两非同构彩色作品的最大可选数量模 $2$。

输入格式

第一行输入 $t$。每组输入颜色数 $n$，以及每种颜色的区间 $l_i,r_i$。

输出格式

每组输出 0 或 1。

样例

4
2
0 1
0 1
2
1 1
1 1
3
0 2
0 1
0 1
3
1 2
1 1
1 1

1
0
1
1