Minimum Cut

Time Limit: 3000/2000 MS (Java/Others)

Memory Limit: 65535/102400 K (Java/Others)

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

Case #1: 2

Hint

wange2014

Source

2015 ACM/ICPC Asia Regional Shenyang Online

提交代码