問題文

ラスク君は $K$ 頂点からなる木 $T_1$ を持っています。頂点には $1, 2, \ldots , K$ の番号がついており、$i$ 番目 ($1\leq i \leq K-1$) の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。はじめ、$T_1$ のすべての辺は赤色で塗られています。

ラスク君は、$T_1$ に次の $2$ 種類の操作を好きな順に何回でも行うことができます。全く操作を行わなくても構いません。

1. $T_1$ の頂点 $v$ を選ぶ。新しい頂点 $w$ を追加し、青色の辺 $(v, w)$ を追加する。
2. $T_1$ の辺 $(u, v)$ を選ぶ。辺 $(u, v)$ の色を $x$ とする。新しい頂点 $w$ を追加し、辺 $(u, v)$ を取り除いて、色 $x$ の辺 $(u, w), (v, w)$ を追加する。

ラスク君には、お気に入りの木 $T_2$ があります。$T_2$ は $N$ 頂点からなり、頂点には $1, 2, \ldots , N$ の番号がついていて、$i$ 番目 ($1\leq i \leq N-1$) の辺は頂点 $c_i$ と頂点 $d_i$ を結んでいます。

ラスク君の目標は、$T_1$ を $T_2$ と同型にすることです (同型判定において、辺の色は考慮しません)。これが可能かどうか判定し、可能な場合は最終的な $T_1$ における赤色の辺の本数の最大値を求めてください。

入力

$K$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{K-1}\ b_{K-1}$
$N$
$c_1\ d_1$
$c_2\ d_2$
$\vdots$
$c_{N-1}\ d_{N-1}$

• $2\leq K\leq N\leq 100$
• $1\leq a_i < b_i\leq K$
• $1\leq c_i < d_i\leq N$
• 入力で与えられるグラフはいずれも木である。
• 入力はすべて整数である。

出力

$T_1$ を $T_2$ と同型にすることが不可能な場合は -1 と出力してください。可能な場合は、最終的な $T_1$ における赤色の辺の本数として考えられる最大値を出力してください。

サンプル

4
1 3
3 4
2 3
6
4 5
1 6
1 3
2 5
1 5

4

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

-1

5
2 5
1 5
2 4
2 3
10
7 9
1 8
6 9
8 10
6 8
3 10
5 8
4 8
2 5

7