Problem Description

Xiao Lan is team building with friends, and there is a game that requires two people to cooperate. Each person is given a tree of size $n$ and $m$, respectively, where each node on the tree has a positive integer weight.
The two participants need to start from the root node $1$ of their respective trees and move towards a leaf node. The sequence of positive integers formed by the weights of all nodes on the path from the root to this leaf node is their sequence. The longest common prefix of the two sequences is their score. Given the two trees, calculate the maximum score the two participants can achieve.

Input Format

The first line of input contains two positive integers $n$ and $m$, separated by a space.
The second line contains $n$ positive integers $c_1, c_2, \cdots, c_n$, separated by spaces, where $c_i$ represents the weight of node $i$ on the first tree.
The third line contains $m$ positive integers $d_1, d_2, \cdots, d_m$, separated by spaces, where $d_i$ represents the weight of node $i$ on the second tree.
The next $n - 1$ lines each contain two positive integers $u_i$ and $v_i$, indicating that there is an edge between nodes $u_i$ and $v_i$ in the first tree.
The next $m - 1$ lines each contain two positive integers $p_i$ and $q_i$, indicating that there is an edge between nodes $p_i$ and $q_i$ in the second tree.

Output Format

Output a single line containing an integer representing the answer.

Sample Input and Output

Input Sample #1

2 2
10 20
10 30
1 2
2 1

Output Sample #1

1

Input Sample #2

5 4
10 20 30 40 50
10 40 20 30
1 2
1 3
2 4
3 5
1 2
1 3
3 4

Output Sample #2

2

Notes

For $20\%$ of the test cases, $1 \leq n, m \leq 500$;
For all test cases, $1 \leq n, m \leq 2 \times 10^5$, $1 \leq c_i, d_i \leq 10^8$, $1 \leq u_i, v_i \leq n$, $1 \leq p_i, q_i \leq m$, and for any node, the weights of its child nodes are distinct.

见题面 Input 部分

见题面 Output 部分