某国有n个城市，编号为1~n。这些城市两两之间都有一条双向道路（一共有$\frac{n(n-1)}{2}$条），其中一些道路上有妖怪，其他路是安全的。为了保证城市之间两两可达，你第一天晚上住在城市1，然后白天随机选择一个新的城市，然后顺着它与当前所在城市之间的道路走过去，途中消灭这条路上所有的妖怪，晚上住在这座城市。在平均情况下，需要多少个白天才能让任意两个城市之间均可以不经过所有妖怪的道路而互相可达？

输入的第一行为数据组数T($T\leq100$)。每组数据的第一行为两个正整数n和m($1\leq n\leq 30,0\leq m\leq \frac{n(n-1)}{2}$)，即城市的数目和安全道路的数目；以下m行每行两个整数a和b($1\leq a,b\leq n$)，表示链接两个城市a和b的道路是安全的（即没有妖怪）。

对于每组数据，输出平均情况下需要的白天数目。