AT_utpc2013_03.直径

题目背景

鳗鱼王国有一个名为鱼鳗王国的邻国。这两个王国都有许多的大城市，这些城市之间有一些道路相连。然而现在，鳗鱼王国和鱼鳗王国之间没有互通的道路。所以，鳗鱼王国的国王殿下为了和鱼鳗王国构筑友好关系，打算在两个城市间建设一条道路，因为有很多条可以建设的道路，对运费很敏感的国王殿下想知道两两城市间最短距离的最大值。
给出顶点数 $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】

请注意此处的最小值。