370 . Matching
Description
A matching M in a graph is a set of edges, where two edges do not share any endpoints.
Now given a graph, please find the maximum matching in it.
Input Format
First line contains an integer t, indicating the number of testcases.
Following is t blocks of input specification, each with the following format:
Two integers n and m on the first line, representing the number of vertices and edges.
Then n lines each containging two integers v and u, which describes the two endpoints an edge connects.
There "may" be arbitrary whitespaces in the input file, though.
Multiedge and self-cycles are not forbidden, either.
Constraints:
1<=n<=500
0<=m<=20000
Output Format
Output an integer in one line for each single test case.
The integer should represent the maximum number of matching in the given graph.
Sample Input 1
2 12 13 11 1 1 3 1 2 2 3 2 4 4 6 2 6 2 5 5 7 7 2 7 8 8 9 8 10 3 2 1 2 2 0
Sample Output 1
5 1
Hints
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|