Description
给定一个无向图，小兔齐齐一开始位于某个节点上(我们不知道他具体在哪个节点上)。我们知道每一秒小兔都必定会向他所在的节点的某一个邻居节点出发(如果存在邻居节点；假设小兔的移动速度很快，移动时间可以忽略)。在每一秒你可以做不超过2次的询问,每次可以询问某个节点是否有小兔！
现在假设小兔不想被我们找到，同时小兔非常聪明，那么我们需要至少几秒才能必定找到小兔的位置？
Input
输入数据第一行包含一个整数T，表示测试数据的组数。对于每组测试数据：
第一行输入两个整数N和M , N图中的节点，M表示边数，1 <= N <= 15 ,1 <= M <= 100 。
接下来输入M行，每行2个正整数 x y, 表示x和y直接有一条边(不存在自环)。 1<=x,y<=N
Output
对于每组数据输出一行，如果你最终可以找到小兔，输出最坏情况下需要几秒才能知道小兔的目前位置;否则输出一个 "-1" (不包括引号)
Sample Input
2
3 3
1 2
2 3
3 1
4 3
1 2
2 3
3 1
Sample Output
1
2
Hint
第一组样例中: 第1秒查询节点1和2，如果小兔在1或2，则解决；否则小兔必然在3；
第二组样例中: 第1秒查询节点1和2，如果小兔在1或2，则解决;否则小兔可能在3或者4。第2秒查询节点1和2，如果在1或者2，则解决；否则小兔必然在4(如果前1秒是在节点3，那么这一秒肯定不在1就在2)。
这题是状压dp，真的很巧妙，我是看了别人ac代码才想通的，表示网上找不到相关题解。
简单来说，状态i中的1表示这个点已经确定，dp[i]表示的是确定状态i的最少时间。
那么对于每个点，当从这个点出去的所有点都已经确定的时候，那这个点就确定了，
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x7FFFFFFF;
const int maxn = 1 << 16;
int T, n, m, dp[maxn], f[maxn], x, y;
queue<int> p;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) f[i] = 0;
for (int i = 1; i < (1 << n); i++) dp[i] = INF;
while (m--)
{
scanf("%d%d", &x, &y);
f[x - 1] |= 1 << y - 1;
f[y - 1] |= 1 << x - 1;
}
for (int i = 0; i < n; i++) if (!f[i]) f[i] = 1 << i;
while (!p.empty()) p.pop(); p.push(0);
while (!p.empty())
{
int q = p.front(); p.pop();
int now = 0;
for (int i = 0; i < n; i++) if ((q&f[i]) == f[i]) now |= 1 << i;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (dp[now | (1 << i) | (1 << j)] > dp[q] + 1)
{
dp[now | (1 << i) | (1 << j)] = dp[q] + 1;
p.push(now | (1 << i) | (1 << j));
}
}
}
}
int k = (1 << n) - 1, ans = dp[k];
for (int i = 0; i < n; i++) ans = min(ans, dp[k ^ (1 << i)]);
if (ans == INF) printf("-1\n"); else printf("%d\n", ans);
}
return 0;
}