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.
|
|
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 |