F: 木を隠すのなら森の中

物語

「木はいいです」 喫茶店「タートルハウス」を経営するチコちゃんは、木に並々ならぬ愛情を持っている。なんでも、木の不動のあり方に心が洗われるらしい。。。そんなチコちゃんの木への愛情を確かめるため、同じ喫茶店でバイトをしているココロちゃんはチコちゃんにいたずらを仕掛けることにした。

ココロちゃんは、チコちゃんのために森を用意して、喫茶店近くに生えていた木を何本か森の中に隠し、チコちゃんの木への愛情を試すことにした。具体的には、チコちゃんに、隠した木を森の中から見つけてもらうことにした。木をこよなく愛するチコちゃんなら、一度見たことがある木は、心の洗われ方の違いでわかるのだが、木を移動してしまったため、木の不動のあり方が変わってしまい、どの木が喫茶店近くにあった木かわからなくなってしまった。しかも、ドジなココロちゃんも答えの木がどれか忘れてしまった！このままでは答えの木を元の場所に戻せないので、ココロちゃんがチコちゃんに怒られてしまう。そこで、優しいプログラマーの皆さんでココロちゃんに答えの木が何本あるのか教えてあげるプログラムを書いてあげよう。

問題

入力として、2つのグラフG_1とG_2が与えられる。G_1は森、つまり閉路のないグラフ（連結とは限らない）で、G_2は木、つまり閉路のない連結なグラフである。このとき、G_1がG_2と同型な連結成分をいくつ持つのかを求めよ

注1）グラフG_1のある連結成分H_1に含まれる任意の2頂点u, vに対して、u, vが隣接する場合にのみ、G_2中の2頂点f(u), f(v)が隣接するような全単射fが存在するとき、H_1は、G_2と同型なG_1の連結成分であるという。

入力

入力は以下の形式で与えられる。

N_1 M_1
u_1 v_1
...
u_{M_1} v_{M_1}
N_2
w_1 x_1
...
w_{N_2 - 1} x_{N_2 - 1}

1行目では、森G_1の頂点数N_1（1 \leq N_1 \leq 300,000）と辺数M_1（0 \leq M_1 \leq N_1 - 1）が与えられる。続くM_1行では、i行目でG_1のi番目の辺e_iが与えられる(1 \leq i \leq M_1)。e_iは2頂点u_iとv_iをつなぐ辺である。（1 \leq u_i, v_i \leq N_1, u_i \neq v_i）次の行には木G_2の頂点数N_2（1 \leq N_2 \leq 30,000）が与えられる。続くN_2 - 1行では、j行目でG_2のj番目の辺e_jが与えられる(1 \leq j \leq N_2 - 1)。e_jは2頂点w_jとx_jをつなぐ辺である。（1 \leq w_j, x_j \leq N_2, w_j \neq x_j）

出力

G_1の持つG_2と同型な連結成分の数を出力せよ。

入力例1

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

出力例1

1

入力例2

14 9
5 8
5 11
10 14
6 4
13 9
3 14
1 2
6 12
7 9
3
3 1
2 1

出力例2

4