## Same Tree

Points: 100
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Python

You are given two binary trees $$T_1$$ and $$T_2$$ with $$N$$ nodes each.

Check whether the both the trees are similar to each other.

Two trees are similar if they have same structure and value of corresponding nodes is also equal.

#### Input

First line contains single integer: $$N$$.

Following lines of input describe the $$T_1$$ and $$T_2$$.

First line contains single integer : $$root$$

Next line contains $$N$$ intgers, where $$i^{th}$$ integer is the value of node with index $$i$$.

Next $$N$$ lines contains two integers each, index of left child and right child of node with index $$i$$. If any of integer is $$-1$$ then corresponding child is absent.

#### Output

Ouput YES if trees are similar, otherwise print NO.

#### Constraints

$$1$$ $$\leq$$ $$N$$ $$\leq$$ $$10^5$$

$$0$$ $$\leq$$ $$value[i]$$ $$\leq$$ $$10^9$$

##### Example

Input

3
2
2 3 1
-1 -1
1 3
-1 -1
1
3 1 2
2 3
-1 -1
-1 -1

Output

YES

Note

You can use this template to submit the solution.

## Comments

• commented on June 6, 2021, 9:30 p.m.

Sample Test case is Wrong *corrected Test case is** 3 2 2 3 1 -1 -1 1 3 -1 -1 1 3 1 2 3 2//*** -1 -1 -1 -1