直径

### 题目背景 鳗鱼王国有一个名为鱼鳗王国的邻国。这两个王国都有许多的大城市，这些城市之间有一些道路相连。然而现在，鳗鱼王国和鱼鳗王国之间没有互通的道路。所以，鳗鱼王国的国王殿下为了和鱼鳗王国构筑友好关系，打算在两个城市间建设一条道路，因为有很多条可以建设的道路，对运费很敏感的国王殿下想知道两两城市间最短距离的最大值。 ### 题目描述 给出顶点数 $n_1$，边数 $m_1$ 的无向图 $G_1$ 和顶点数 $n_2$，边数 $m_2$ 的无向图 $G_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$ 图中有一条以 $a_i,b_i$ 为顶点的边。接下来一行为图 $G_2$ 的顶点数 $n_2$ 和边数 $m_2$。接下来的 $m_2$ 行为边的情况。$c_i,d_i$ 表示 $G_2$ 图中有一条以 $c_i,d_i$ 为顶点的边。 ### 输出格式 将在两个图间加一条边得到的图的直径最小值与最大值以空格分开输出。 ### 说明/提示 #### 数据范围 输入中的各变量满足以下条件。 - $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<n_1$ - $0\leq c_i,d_i<n_2$ - 每张图为连通图 - 每张图为简单图，也就是说没有重边与自环。 对于 $50\%$ 的数据，$1\leq n_1,n_2\leq20$。 #### 样例解释 【样例解释 1】 直径为 $3$ 及直径为 $5$ 的情况见下图：  【样例解释 2】 直径为 $7$ 及直径为 $11$ 的情况见下图：  【样例解释 3】 请注意此处的最小值。

うなぎ王国の隣にはうさぎ王国がある．各王国には沢山の都市があり，都市間には道路がひかれている．現在，うなぎ王国とうさぎ王国を行き来する道路は存在しない．そこで，うなぎ王国の王様はうさぎ王国と友好関係を築くため，$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$ 行に出力せよ．

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

3 5

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

7 11

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

6 8

### 制約 入力中の各変数は以下の制約を満たす． - $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<n_1$ - $0\leq c_i,d_i<n_2$ - 各グラフは連結である - 各グラフは単純である，すなわち多重辺やループは含まれない #### 部分点 この問題には部分点が設定されている．この問題のテストケースのうち $50$ 点分は、追加で以下の制約も満たす． - $1\leq n_1,n_2 \leq 20$