Question

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 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. The graph has no cycles or self-loops.
using C++

Answer 1

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 ≤ 104

1 ≤ M ≤ 105

1 ≤ X, Y ≤ N