Link: Arbiter

Input

The first line of input consists of an integer T, indicating the number of test cases.

The first line of each case consists of two integers N and M, indicating the number of stars and the number of channels. Each of the next M lines indicates one channel (u, v) which means there is a bidirectional channel between star u and star v (u is not equal to v).

Output

Output one integer on a single line for each case, indicating the minimum number of channels KMXS must prohibit to avoid mental disorder.

Constraints

0 < T <= 10

0 <= N <= 15 0 <= M <= 300

0 <= u, v < N and there may be more than one channel between two stars.

Sample Input

1

3 3

0 1

1 2

2 0

Sample Output

1

Problem solving:

这道题的题意我没看。但是让你求的就是给你一个平凡图，问你最少需要删几条边使得图中没有奇环（即一个环是由奇数个边连起来的）。

上海站的那道题跟这个简直一模一样，枯了。

二分图，一个图是二分图的充要条件是图中所有的环都是偶环，全都是偶环也就是没有奇环。并且这个题目数据范围也不大，最多还不到16个点，所以我们可以使用二进制枚举来写。二进制位是0的是二分图的一边，是1的就是二分图的另一边，如果出现在同一边的两个点之间有一条边，删除即可。枚举每一种情况，16个点，2^16种情况，每次更新最小值即可。

Code:

```
#include <iostream>
using namespace std;
const int maxn = 521;
struct node
{
int u, v;
} a[maxn];
int main()
{
int t, n, m;
cin >> t;
while (t--)
{
int ans = 0x3f3f3f3f;
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> a[i].u >> a[i].v;
for (int i = 0; i < (1 << n); i++)
{
int mid = 0;
for (int j = 0, u, v; j < m; j++)
{
u = a[j].u, v = a[j].v;
if (((i >> u) & 1) == ((i >> v) & 1))
mid++;
}
ans = min(ans, mid);
}
cout << ans << endl;
}
return 0;
}
```

反思一下：二分图和二进制枚举也不是没学过，不会使用，真的是自己的锅，以后加油！