题目描述

某个国家有 $N$ 个滑雪度假站，编号为 $1$ 到 $N$。它们之间有 $N-1$ 条双向道路，并且任意两个滑雪站之间都可以通过若干道路到达。因此这些滑雪站形成一棵树。

滑雪季共有 $M$ 周，编号为 $1$ 到 $M$。每一周，滑雪者 Marcel 都会访问一个滑雪站，并在自己的笔记本中记录每个滑雪站最后一次被访问的周数。

由于交通成本很高，Marcel 在相邻两周访问的滑雪站之间必须有一条直接道路。也就是说，他每周会沿树上的一条边走到相邻滑雪站。注意，Marcel 不会在连续两周访问同一个滑雪站。

滑雪季结束后，Marcel 从笔记本中给出 $N$ 个数：

其中 $v_i$ 表示他最后一次访问滑雪站 $i$ 的周数。

你看到这些数后并不完全相信他，因此想判断：这些记录是否可能来自某一次真实的滑雪路线，还是 Marcel 一定抄错了。

你需要对 $T$ 个互相独立的场景分别判断。

输入中不单独给出 $M$。若记录合法，则最后一周一定发生在某个滑雪站，因此可理解为 $M=\max_i v_i$。

输入格式

第一行一个整数 $T$，表示场景数。

接下来依次给出 $T$ 个场景。每个场景格式如下：

第一行一个整数 $N$，表示滑雪站数量。

第二行 $N$ 个整数：

接下来 $N-1$ 行，每行两个整数 $a,b$，表示滑雪站 $a$ 与 $b$ 之间有一条双向道路。

输出格式

输出一行，由 $T$ 个二进制字符组成。

第 $i$ 个字符表示第 $i$ 个场景的答案：

• 若 Marcel 的记录可能为真，输出 1；
• 若 Marcel 一定抄错了，输出 0。

约束与说明

• $1\le T\le 15000$
• $2\le N\le 100000$
• $2\le M\le 100000000000$
• Marcel 每个滑雪站至少访问一次，因此 $1\le v_i\le M$
• 所有场景的 $N$ 之和不超过 $400000$

由于输入中没有单独给出 $M$，实际读入时可以把 $v_i$ 看作满足 $1\le v_i\le 10^{11}$ 的整数。

子任务

样例 1

输入

1
6
11 6 5 3 10 9
1 2
2 3
2 4
1 5
5 6

输出

1

样例 2

输入

2
9
10 9 8 13 1 7 12 14 6
1 2
1 4
2 3
3 5
3 6
6 9
4 7
4 8
4
5 4 5 3
1 2
1 3
2 4

输出

10

样例解释

对于样例 1，Marcel 可以按如下顺序访问滑雪站：

4, 2, 4, 2, 3, 2, 1, 5, 6, 5, 1

对于样例 2 的第一个场景，Marcel 可以按如下顺序访问滑雪站：

5, 3, 6, 9, 6, 9, 6, 3, 2, 1, 4, 7, 4, 8

对于样例 2 的第二个场景，记录不可能成立，因为它要求 Marcel 在同一时间既位于滑雪站 $1$，又位于滑雪站 $3$。