Minimum Cut

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≤t≤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≤n≤20000) and m (n−1≤m≤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

查看全部
shunfurh
编程介的小学生
2016/11/12 11:02
  • lines
  • 点赞
  • 收藏
  • 回答
    私信
满意答案
查看全部

2个回复