Monk visits the land of Islands.  There are a total of N islands numbered from 1 to N.  Some pairs of islands are connected to each other by Bidirectional bridges running over water.
Monk hates to cross these bridges as they require a lot of efforts. He is standing at Island #1 and wants to reach the Island #N. Find the minimum the number of bridges that he shall have to cross, if he takes the optimal route.   

Input:
First line contains T. T testcases follow.
First line of each test case contains two space-separated integers N, M.
Each of the next M lines contains two space-separated integers X and Y , denoting that there is a bridge between Island X and Island Y.  

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10^4
1 ≤ M ≤ 10^5
1 ≤ X, Y ≤ N

SAMPLE INPUT
2
3 2
1 2
2 3
4 4
1 2
2 3
3 4
4 2

SAMPLE OUTPUT
2
2
'__author__'=='deepak Singh Mehta(learning to code :) ) '
 
'''
    Hard work beats Talent when Talent doesn't work hard. :)
 
'''

int_max = 10000000

if __name__=='__main__':
    tests = int(raw_input())
    for _ in range(tests):
        n,m = map(int,raw_input().split())
        graph =[[] for i in range(n+1)]
        for _ in range(m):
            x,y = map(int,raw_input().split())
            graph[x].append(y)
            graph[y].append(x)
        vis = [ False for i in range(n+1)]
        dist = [ -1 for i in range(n+1)]
        #bfs
        s = 1
        que = list()
        que.append(s)
        vis[s] = True
        dist[s] = 0
        while len(que)!=0:
            u = que[0]
            del que[0]
            for v in range(len(graph[u])):
                if not vis[graph[u][v]]:
                    dist[graph[u][v]] = dist[u] + 1
                    vis[graph[u][v]]=True
                    que.append(graph[u][v])
        print dist[n] if dist[n]!=-1 else -1