Description

小Y喜欢跳增员操，所以他建了个群‘‘小Y增员操直播群’’，向大家直播他的增员操。这个群每天都能增到许多优秀的成员。具体来说，它每天都可能会和其他的增员操直播群（比如kblack增员操直播群）合并。

每个增员操直播群的群成员都有一个编号。对于任意一个\(n\)人的群，所有人的编号是从\(0\)到\(n-1\)的。\(2\)个群合并的过程是这样的：先找出一个人数较少的群（如果两群人数相等则随便挑选一个）\(A\)，假设其人数为\(n_a\)。接着我们将另一人数较多的群\(B\)的所有成员的编号都加上\(n_a\)，并将这些成员全部加入群\(A\)。众所周知，OI圈中互膜盛行。当\(2\)个群合并时，他们之间的一些群成员会进行互膜。对于每个原\(B\)群中的成员，假设其在新群中的编号为\(i\)（显然有\(i<n_a\)），那么他会与新群中编号为\(i \mod n_a\) 的成员互膜。

需要注意的是，每个增员操直播群建群时都只有\(1\)人，并且除了合并之外，任何增员操直播群都没有其他的增员方式。除此之外，一个群在一天内只能参与一次合并，也就是说在某一天合并而成的新群在当天不能再次参与合并。

经过了\(d\)天的合并，全世界的所有增员操直播群都被合并到了小Y增员操直播群。小Y的粉丝wangyurzee对小Y增员操直播群非常感兴趣，他想知道这个群现在的人数，以及这个群里所有人的互膜历史（包括之前所有合并时进行的互膜）。小Y想了一想，告诉他：‘‘现在小Y增员操直播群共有n个成员和m条互膜记录。’’ 接着，小Y向wangyurzee描述了每一条互膜记录。由于小Y经常意识模糊，所以wangyurzee将信将疑，他找到了即将参加NOI的你，请你帮他验证这个群是否能够通过合法的合并操作得到这些互膜记录。如果答案是肯定的，wangyurzee还想知道\(d\)最小是多少。你能帮帮他吗？

Input

本题有多组数据，第一行一个整数\(T\)，表示数据组数。接下来依次描述各组数据，对于每组数据：第一行\(2\)个整数\(n,m\)，意义见题目描述。

接下来m行，每行2个整数\(u, v\)，描述了当前群内编号为u的成员和当前群内编号为v的成员曾经互膜过一次（他们进行这次互膜时的编号并不一定为u和v）。

需要注意的是，这些互膜记录并不一定是按时间顺序给出的。

Output

对于每组数据，输出一行：如果该群不合法，输出\(-1\)，否则输出最小的\(d\)。

Sample

Input

2
3 3
0 1
0 2
1 2
4 6
0 1
1 2
2 3
3 0
0 2
1 3

Output

2
3

Hint

对于10%的数据，保证\(T=1\)。
对于20%的数据，保证\(n\le 10，m\le 10\)。
对于50%的数据，保证\(n\le 1000\)。
对于100%的数据，保证$T\le 10，1\le n\le 100000，0\le m\le 100000，0\le u, v < n。