問題
背景
鳗鱼王国旁边是兔子王国。每个王国都有许多城市,城市之间修建了道路。目前,鳗鱼王国和兔子王国之间没有往返的道路。因此,鳗鱼王国的国王想与兔子王国建立友好关系。2两国城市之间的道路1我正在考虑建造它。由于可以修建的道路有很多条,对交通成本敏感的国王想知道城市之间最短距离的最大值是多少。
課題
頂点数 n1,辺数 m1 的无向图 G1 和顶点数 给出了 n2,辺数 m2 的无向图 G2 。每个图都是相连的。也就是说,对于每个图,任意2有一条连接顶点的路径。你是1添加书面2我正在尝试连接两个图表。您可以以任何您喜欢的方式添加边缘。生成的图形上两个最远点之间的最小和最大距离是多少(称为图形的直径)?
配点
100
入力
输入按以下格式给出。
n1 m1 a1 b1 a2 b2 ... am1 bm1 n2 m2 c1 d1 c2 d2 ... cm2 dm2
第一行有一个图表 G1 中的顶点数 n1 和边数 给出了 m1 。继续 m1 行提供边缘信息。 在 ai,bi 是 G1 中2頂点 ai,bi 表示它们之间有一条边。下一行有一个图表 G2 中的顶点数 n2 和边数 给出了 m2 。继续 m2 行提供边缘信息。 在 ci,di 是 G2 中2頂点 ci,di 表示它们之间有一条边。
制約
输入中的每个变量都满足以下约束。
- 1 \leq n1,n2 \leq 1000 (=103)
- 0 \leq m1,m2 \leq 10000 (=104)
- 0 \leq ai,bi \lt n1
- 0 \leq ci,di \lt n2
- 每个图都是相连的
- 每个图都很简单,即不包含多个边或环。
部分点
针对此问题设置了部分分数。这个问题的测试用例50这些点还满足以下约束。
- 1 \leq n1, n2 \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的示例如下。
図 1
入力例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的示例如下。
図 2
入力例3
7 6 0 1 1 2 2 3 3 4 4 5 5 6 2 1 0 1
输入示例 3 的输出示例
6 8
注意生成的图形的最小直径。