Land of Islands

Time Limit: 3 sec

 

The Problem

Rahat kamal (Known as [B** Kamal] at BGC ) 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.

 

Rahat kamal(B** Kamal) 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.

 

The Input

First line contains T(1 ≤ T ≤ 10) denoted the number of test cases. T test cases follow.

First line of each test case contains two space-separated integers N(1 ≤ N ≤ 1004), M(1 ≤ M ≤ 1005). Each of the next M lines contains two space-separated integers X(1 ≤ X ≤ N) and Y(1 ≤ Y ≤ N) , denoting that there is a bridge between Island X and Island Y.

 

The Output

For each test case you have to print a line of output, this line contains an integer number which the minimum number of bridges that (B** Kamal) shall have to cross.

 

Sample Input

2

3 2

1 2

2 3

4 4

1 2

2 3

3 4

4 2

 

Sample Output

2

2

 

 

 

Inter University Programming Contest - 2017 [BGC Trust University Bangladesh]

Problem Setter: Parag Paul