Minimum Cut

Given a simple unweighted graph $G$ (an undirected graph containing no loops nor multiple edges) with $n$ nodes and $m$ edges. Let $T$ be a spanning tree of $G$.
We say that a cut in $G$ respects $T$ if it cuts just one edges of $T$.

Since love needs good faith and hypocrisy return for only grief, you should find the minimum cut of graph $G$ respecting the given spanning tree $T$.

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

Each test case contains several lines.
The first line contains two integers $n~(2\le n\le 20000)$ and $m~(n-1\le m\le 200000)$.
The following $n-1$ lines describe the spanning tree $T$ and each of them contains two integers $u$ and $v$ corresponding to an edge.
Next $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 not in the spanning tree $T$.

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

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

Case #1: 2

2015 ACM/ICPC Asia Regional Shenyang Online