LTCS

题号：NC239321
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Tcs has just learned the subsequence of a sequence. Now Tcs wants to define the subsequence of a rooted tree. A rooted tree $T_a$ which satisfies the following constraints is called a subsequence of another rooted tree $T_b$ :

Suppose that there are $N$ vertices in $T_a$ numbered as $1,2,\ldots,N$ and there are $M$ vertices in $T_b$ numbered as $1,2,\ldots,M$ . There is a function $F:\{1,2,\ldots,N\} \to \{1,2,\ldots,M\}$ , which satisfies $\forall x, y \in \{1,2,\ldots,N\}, x \ne y \Rightarrow F(x) \not = F(y)$ .
For all vertices $u$ in $T_a$ , $c_{a, u} = c_{b, F(u)}$ holds, where $c_{i, u}$ is the value of vertex $u$ in $T_i$ .
If vertex $u$ is an ancestor of vertex $v$ in $T_a$ , then vertex $F(u)$ is an ancestor of vertex $F(v)$ in $T_b$ .
For distinct vertices $u, v, w$ in $T_a$ , if vertex $u$ is the father of both vertex $v$ and vertex $w$ , then vertex $F(u)$ is on the simple path between vertex $F(v)$ and vertex $F(w)$ in $T_b$ .

A rooted tree $T_3$ is called a TCS (Tree Common Subsequence) of $T_1$ and $T_2$ when $T_3$ is a subsequence of both rooted trees $T_1$ and $T_2$ . Given the rooted trees $T_1$ and $T_2$ whose roots are both vertex $1$ , Tcs wants to find the largest size of the TCS of $T_1$ and $T_2$ .

输入描述:

The first line contains two integers  () — the number of vertices in  and , respectively.

The second line contains  integers  () — the value of each vertex in .

The third line contains  integers  () — the value of each vertex in .

Each of the next  lines contains two integers  and  () — an edge connecting vertices  and  in . 

Each of the next  lines contains two integers  and  () — an edge connecting vertices  and  in .

输出描述:

Print an integer in a single line, denoting the largest size of the TCS of  and .

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制