問題

背景

うなぎ王国の隣にはうさぎ王国がある．各王国には沢山の都市があり，都市間には道路がひかれている．現在，うなぎ王国とうさぎ王国を行き来する道路は存在しない．そこで，うなぎ王国の王様はうさぎ王国と友好関係を築くため，2つの王国の都市間に道路を1本建設しようと考えている．建設候補となる道路は沢山あるため，運送コストに敏感な王様は都市間の最短距離の最大値がどのような値をとるかを知りたがっている．

課題

頂点数 n₁，辺数 m₁ の無向グラフ G₁ と頂点数 n₂，辺数 m₂ の無向グラフ G₂ が与えられる．各々のグラフは連結である．すなわち，各グラフについて，任意の2頂点を結ぶ経路が存在する．あなたは，1本の辺を追加して2つのグラフを連結にしようと思っている．辺はどのように追加しても構わない．出来上がるグラフ上で最も遠い２点間の距離(グラフの直径と呼ばれる)が最小・最大いくつになるか答えよ．

配点

100

入力

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

n1 m1
a1 b1
a2 b2
...
am1 bm1
n2 m2
c1 d1
c2 d2
...
cm2 dm2

最初の行にはグラフ G₁ の頂点数 n₁ と辺数 m₁ が与えられる．続く m₁ 行には辺の情報が与えられる． a_i，b_i は G₁ において2頂点 a_i，b_i 間に辺があること意味する．次の行にはグラフ G₂ の頂点数 n₂ と辺数 m₂ が与えられる．続く m₂ 行には辺の情報が与えられる． c_i，d_i は G₂ において2頂点 c_i，d_i 間に辺があること意味する．

制約

入力中の各変数は以下の制約を満たす．

• 1 \leq n₁,n₂ \leq 1000 (=10³)
• 0 \leq m₁,m₂ \leq 10000 (=10⁴)
• 0 \leq a_i,b_i \lt n₁
• 0 \leq c_i,d_i \lt n₂
• 各グラフは連結である
• 各グラフは単純である，すなわち多重辺やループは含まれない

部分点

この問題には部分点が設定されている．この問題のテストケースのうち50点分は、追加で以下の制約も満たす．

• 1 \leq n₁, n₂ \leq 20

出力

2つのグラフの間に辺を1本追加してできあがるグラフの直径の最小値・最大値を空白スペース区切りで1行に出力せよ．

入力例1

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

入力例1に対する出力例

3 5

直径が3になる例と5になる例はそれぞれ以下の通り．

入力例2

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

入力例2に対する出力例

7 11

直径が7になる例と11になる例はそれぞれ以下の通り．

入力例3

7 6
0 1
1 2
2 3
3 4
4 5
5 6
2 1
0 1

入力例3に対する出力例

6 8

できあがるグラフの直径の最小値に注意せよ．