Alice and Bob broke up finally. There are n cities, there is either a road or a railway between every two cities. There is a railway between two cities if and only if there are no road between these cities. Each road and railway will cost 1 time unit. Now Alice and Bob are in the city 1. They want to arrive at the city n. But they do not want to arrive at any cities at the same time (except city 1 and city n). And they also do not want to take the same vehicle. Alice will take the bus and Bob will take the train. Could you find the minimum time that Alice and Bob both arrive at the city n? If some of them can not arrive at n or they have to meet some cities at the same time, print -1.

All cities are labeled from 1 to n.

Note: There are no multiple roads or railways between two cities.

The first line will be an integer T. (1 <= T <= 50) T is the number of test case.

For each test case, the first line will be two integers n and m. (1 <= n <= 1234, 0 <= m <= n(n-1)/2)

n is the number of cities and m is the number of roads.

Then there will be m lines. Each line will contain two integers x y. Means there is a road between x and y.

For each test cast, print the minimum time or -1.

For the first sample, A go to this path on
roads: 1->3->4, B go to this path on trains: 1->2->4

They will arrive at 4 at the same time. The
answer is 2.

For the second sample, there are no trains.
B can’t arrive at 4. The answer is -1.