Cho ~N~ hòn đảo (đánh số từ 1 đến ~N~) được nối với nhau bởi ~M~ cây cầu. John là một người rất yêu thể thao nhưng lại ngại qua cầu. Bạn hãy giúp John tìm đường đi từ đảo thứ 1 đến đảo thứ ~N~ sao cho đi qua ít cây cầu nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~T~

Với mỗi test case

• Dòng đầu tiên chứa hai số nguyên ~N~, ~M~.

• ~M~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~X~, ~Y~. Kí hiệu rằng có cây cầu nối giữa hai đảo ~X~ và ~Y~.

Dữ liệu ra:

• Với mỗi test case ghi ra file BISLAND.OUT một số nguyên là số lượng cây cầu tối thiểu trên đường đi từ đảo 1 đến đảo N, mỗi kết quả trên 1 dòng.

Ràng buộc:

• ~1 ≤ T ≤ 10~

• ~1 ≤ N ≤ 10^4~

• ~1 ≤ M ≤ 10^5~

• ~1 ≤ X, Y ≤ N~

Ví dụ:

Input:

2
3 2 
1 2 
2 3 
4 4 
1 2 
2 3 
3 4 
4 2

Output:

2 
2