给定一棵二叉树，请判断它是否关于根节点所在的竖直轴左右对称。

也就是说，根节点的左子树和右子树必须互为镜像：两边对应节点的值相等，并且一边的左子树要与另一边的右子树对应，一边的右子树要与另一边的左子树对应。空树认为是对称的。

输入格式

第一行一个整数 $n$，表示二叉树的节点数。节点编号为 $1$ 到 $n$，根节点编号为 $1$；当 $n=0$ 时表示空树。

当 $n>0$ 时，第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$，其中 $v_i$ 表示节点 $i$ 保存的值。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，分别表示节点 $i$ 的左孩子编号和右孩子编号。编号 $0$ 表示相应孩子不存在。输入保证这些数据构成一棵合法二叉树。

输出格式

如果二叉树左右对称，输出 true；否则输出 false。

6
7 4 7 4 3 2
2 3
4 0
5 6
0 0
0 0
0 0

false

2
3 5
0 2
0 0

false

5
3 4 4 5 5
2 3
4 0
0 5
0 0
0 0

true

数据范围与约定

• 树中节点数目在范围 [1, 1000] 内
• -100 ≤ v_i ≤ 100