Minimum Cut-Cut

Given a simple unweighted graph $G$ (an undirected graph without self-loops or multiple edges) with $n$ nodes and $m$ edges. Let $T$ be a spanning tree of $G$. We say that a cut in G two-respects $T$ if and only if it cuts just two edges of $T$.

Since love needs good faith and hypocrisy return for only grief, you should find the minimum cut of graph $G$ two-respecting given spanning tree $T$. To simplify the problem, we guarantee that for each edge $(u,v)\not\in T$ in graph $G$, the unique path in $T$ between $u$ and $v$ must pass through the node $1$.

The input contains several test cases.
The first line of the input is a single integer $t~(1\le t\le 25)$ which is the number of test cases.
Then $t$ test cases follow.

Each test case contains several lines.
The first line contains the integer $n~(3\le n\le 20000)$ and the integer $m~(n-1\le m\le 100000)$.
The following $n-1$ lines describe the spanning tree $T$ and each of them contains two integers $u$ and $v$ corresponding to an edge.
The following $m-n+1$ lines describe the undirected graph $G$ and each of them contains two integers $u$ and $v$ corresponding to an edge which is no in the spanning tree.

The sum of $m$ for all test cases would not be larger than $500000$.

For each test case, you should output the minimum cut of graph $G$ two-respecting given spanning tree $T$.

2

8 14
1 2
2 3
1 4
4 5
1 6
6 7
6 8
3 4
2 5
5 7
1 7
2 6
2 8
3 8

4 6
1 2
1 3
1 4
2 3
3 4
4 2

Case #1: 3
Case #2: 4

2015ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）