問題文

高橋君は盆栽を 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 つのグラフはそれぞれ木
• 入力は全て整数

入力例 1

4
1 2
2 3
3 4
2
1 2

出力例 1

36

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

入力例 2

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

出力例 2

67