AAC1 - Atul and Aastha Chronicles 1


Aastha and Atul got so into each other during their date that they forgot to keep track of time. Now for students of our college in-time is a very serious issue. If a girl fails to reach her hostel before the stipulated time she will land up in a huge amount of trouble. Aastha doesn't want to land up in trouble so she asks you for help. She will provide you a map with many possible routes to her hostel The map will be a in the form of a set of roads. Your task is to tell her the minimum possible time within which she can reach there. Assume that the time taken to cover each road is 1 unit. Node 1 denotes the starting point and Node n denotes her hostel.

Input

First line contains T. T test cases 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 road between X and 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

Example

Input:
2
3 2
1 2
2 3
4 4
1 2
2 3
3 4
4 2

Output:
2
2

hide comments
vishalshrm539: 2020-08-18 19:39:38

BFS !!

scolar_fuad: 2019-07-08 11:12:48

Simple just saving hight of node

vedsar: 2018-08-22 10:46:15

I'm using BFS and getting wrong answer at 0.06s.
Working fine on sample testcases and my test cases.
Any corner testcase whould be appreciated

nadstratosfer: 2018-06-03 11:23:28

The graph is undirected, you can see the second sample case would yield 3 otherwise. Also you don't need Dijkstra for this.

aquelemiguel: 2018-06-03 04:11:35

One of the most straightforward Dijkstra on SpOJ. Accepts a directed graph and you may consider N the max number of nodes. Bear in mind the node indexes are not 0 based.

vengatesh15: 2017-02-10 07:15:32

easy one AC in 1 go:-)


Added by:Dewang Sultania
Date:2016-03-14
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:MAWK BC C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 C99 COFFEE DART FORTH JAVA JS-RHINO JULIA KTLN OCT PHP PROLOG PYTHON PYPY PYPY3 PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Resource:hackerearth-codemonk