小藍正在和朋友們團建，有一個游戲項目需要兩人合作，兩個人分別拿到一棵大小為 n 和 m 的樹，樹上的每個結(jié)點上有一個正整數(shù)權(quán)值。

兩個人需要從各自樹的根結(jié)點 1 出發(fā)走向某個葉結(jié)點，從根到這個葉結(jié)點的路徑上經(jīng)過的所有結(jié)點上的權(quán)值構(gòu)成了一個正整數(shù)序列，兩人的序列的最長公共前綴即為他們的得分。給出兩棵樹，請計算兩個人最多的得分是多少。

輸入的第一行包含兩個正整數(shù) n, m ，用一個空格分隔。

第二行包含 n 個正整數(shù) c1, c2, · · · , cn ，相鄰整數(shù)之間使用一個空格分隔，其中 ci 表示第一棵樹結(jié)點 i 上的權(quán)值。

第三行包含 m 個正整數(shù) d1, d2, · · · , dm ，相鄰整數(shù)之間使用一個空格分隔，其中 di 表示第二棵樹結(jié)點 i 上的權(quán)值。接下來 n ? 1 行，每行包含兩個正整數(shù) ui, vi 表示第一棵樹中包含一條 ui 和vi 之間的邊。

接下來 m ? 1 行，每行包含兩個正整數(shù) pi, qi 表示第二棵樹中包含一條 pi和 qi 之間的邊。

2 2
10 20
10 30
1 2
2 1

1

【樣例說明】兩個序列可以為 [10, 20] , [10, 30] ，最大前綴為 1 ；

【樣例輸入】

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

【樣例輸出】

2

【樣例說明】

兩個序列可以為 [10, 20, 40] , [10, 20, 30] ，最大前綴為 2 。

【評測用例規(guī)模與約定】

對于 20% 的評測用例，1 ≤ n, m ≤ 500 ；對于所有評測用例，1 ≤ n, m ≤ 2 × 10⁵，1 ≤ ci, di ≤ 108 ，1 ≤ u_i, v_i ≤ n ，1 ≤ p_i, q_i ≤ m ，對于任意結(jié)點，其兒子結(jié)點的權(quán)重互不相同。