Demux Problems Submissions Users Contests Log in Sign up


Same Tree


Submit solution

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


  • 0
    code_demux  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