B - Bonsai Grafting /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700

問題文

高橋君は盆栽を 2 つ購入し、一箇所をつないで接ぎ木をしようとしています。

それぞれの盆栽は、 N 頂点の木 A と、M 頂点の木 B として表すことができます。木 A の辺は、頂点 p_{A_i} と頂点 q_{A_i} (1 ≤ i ≤ N-1) を結んでいます。 木 B の辺は、頂点 p_{B_i} と頂点 q_{B_i} (1 ≤ i ≤ M-1) を結んでいます (ただし、木 A の頂点 i と木 B の頂点 i は別の頂点であることに気をつけて下さい)。

A の頂点 1 つと木 B の頂点 1 つを辺で結ぶことにより、 1 つの N+M 頂点の木を作ることを考えます。 頂点の選び方は合計で NM 通りあります。この NM 通りそれぞれの木について直径 (2 点間にある辺の本数の最大値) を計算し、その合計を求めてください。

制約

  • 2 ≤ N, M ≤ 10^5
  • 1 ≤ p_{A_i}, q_{A_i} ≤ N (1 ≤ i ≤ N-1)
  • 1 ≤ p_{B_i}, q_{B_i} ≤ M (1 ≤ i ≤ M-1)
  • 与えられる 2 つのグラフはそれぞれ木
  • 入力は全て整数

入力

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

N
p_{A_1} q_{A_1}
:
p_{A_{N-1}} q_{A_{N-1}}
M
p_{B_1} q_{B_1}
:
p_{B_{M-1}} q_{B_{M-1}}

出力

NM 通りの木の直径の合計を出力せよ。


入力例 1

4
1 2
2 3
3 4
2
1 2

出力例 1

36

例えば、 A の頂点 2B の頂点 1 を新たに辺で結び、N+M 頂点の木を作ると、直径は 4 となります。


入力例 2

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

出力例 2

67