AT_utpc2013_03 直径

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

[problemUrl]: https://atcoder.jp/contests/utpc2013/tasks/utpc2013_03 頂点数 $n_1$，辺数 $m_1$ の無向グラフ $G_1$ と頂点数 $n_2$，辺数 $m_2$ の無向グラフ $G_2$ が与えられる．各々のグラフは連結である．すなわち，各グラフについて，任意の $2$ 頂点を結ぶ経路が存在する．あなたは，$1$ 本の辺を追加して $2$ つのグラフを連結にしようと思っている．辺はどのように追加しても構わない．出来上がるグラフ上で最も遠い $2$ 点間の距離(グラフの直径と呼ばれる)が最小・最大いくつになるか答えよ．

入力は以下の形式で与えられる. > $n_1$ $m_1$ $a_1$ $b_1$ $a_2$ $b_2$ $\cdots$ $a_{m_1}$ $b_{m_1}$ $n_2$ $m_2$ $c_1$ $d_1$ $c_2$ $d_2$ $\cdots$ $c_{m_2}$ $d_{m_2}$ 最初の行にはグラフ $G_1$ の頂点数 $n_1$ と辺数 $m_1$ が与えられる．続く $m_1$ 行には辺の情報が与えられる．$a_i$，$b_i$ は $G_1$ において $2$ 頂点 $a_i$，$b_i$ 間に辺があること意味する．次の行にはグラフ $G_2$ の頂点数 $n_2$ と辺数 $m_2$ が与えられる．続く$m_2$ 行には辺の情報が与えられる．$c_i$，$d_i$ は $G_2$ において $2$ 頂点 $c_i$，$d_i$ 間に辺があること意味する．

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

### 制約 入力中の各変数は以下の制約を満たす． - $1 \leq n_{1},n_{2} \leq 1000(=10^4)$ - $0 \leq m_{1},m_{2} \leq 10000(=10^5)$ - $0 \leq a_i,b_i