Longest Common Prefix on Two Trees

Two teammates are playing a cooperative game. Each teammate is given a tree. The first tree has n nodes and the second tree has m nodes. Each node in both trees has a positive integer weight. The trees are rooted at node 1. Each player must choose a leaf in his/her tree and consider the unique path from the root (node 1) to that leaf. On that path, the sequence of positive integers is recorded by taking the weights of the nodes in order.

Their score is defined as the longest common prefix of these two sequences. In other words, if one player obtains the sequence \(a_1, a_2, \dots, a_k\) and the other obtains \(b_1, b_2, \dots, b_l\), their score is the maximum integer \(L\) such that \(a_i = b_i\) for all \(1 \le i \le L\). If the weights of the two roots differ then the score is 0.

Given the descriptions of the two trees, compute the maximum score that the two players can achieve by individually choosing a leaf from their respective trees.

Note: The input trees are undirected, but you should consider them as rooted at node 1. A leaf is defined as a node with no children in the rooted tree (except possibly the root if it is the only node).

inputFormat

The input is given as follows:

• The first line contains two integers n and m --- the number of nodes in the first and second tree respectively.
• The second line contains n integers, where the i-th integer represents the weight of node i in the first tree.
• Each of the next n - 1 lines contains two integers u and v meaning there is an edge between nodes u and v in the first tree.
• The following line contains m integers, where the i-th integer represents the weight of node i in the second tree.
• Each of the next m - 1 lines contains two integers u and v describing an edge in the second tree.

You may assume that the trees are valid and that node 1 is the root in both trees.

outputFormat

Output a single integer --- the maximum score (i.e. the maximum number of matching nodes from the root in the two chosen root-to-leaf paths) that can be achieved.

If the weights at the roots of the two trees differ, output 0.

sample

3 3
1 2 3
1 2
1 3
1 2 4
1 2
1 3

2