提示: 欢迎访问OurACM平台。
Problem 2093 寻找兔子

Accept: 52    Submit: 260
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem 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)。

Source

福州大学第九届程序设计竞赛

Submit  Back  Status  Discuss