Problem Description

You are given an undirected graph $G_1$ with $n_1$ vertices and $m_1$ edges, and an undirected graph $G_2$ with $n_2$ vertices and $m_2$ edges. Each graph is connected, meaning there is a path between any two vertices in each graph. You want to connect the two graphs by adding a single edge. The edge can be added in any way. Determine the minimum and maximum possible diameters of the resulting graph.

Input Format

The input is given in the following format:

$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}$

The first line contains the number of vertices $n_1$ and the number of edges $m_1$ for graph $G_1$. The following $m_1$ lines contain edge information. $a_i$ and $b_i$ indicate that there is an edge between vertices $a_i$ and $b_i$ in $G_1$. The next line contains the number of vertices $n_2$ and the number of edges $m_2$ for graph $G_2$. The following $m_2$ lines contain edge information. $c_i$ and $d_i$ indicate that there is an edge between vertices $c_i$ and $d_i$ in $G_2$.

Output Format

Output the minimum and maximum possible diameters of the graph formed by adding a single edge between the two graphs, separated by a space, in one line.

Sample Input and Output

Sample Input #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

Sample Output #1

3 5

Sample Input #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

Sample Output #2

7 11

Sample Input #3

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

Sample Output #3

6 8

Notes/Hints

Constraints

The variables in the input satisfy the following constraints:
- $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$
- Each graph is connected
- Each graph is simple, meaning it does not contain multiple edges or loops

Partial Points

This problem has partial points. For 50 points of the test cases, the following additional constraints are satisfied:
- $1\leq n_1,n_2 \leq 20$

见题面 Input 部分

见题面 Output 部分