Task 4 Dalai Lama is visiting Maldives, the land of a thousand islands. There are a total of N islands in Maldives numbe

[answerhappygod]

Task 4 Dalai Lama Is Visiting Maldives The Land Of A Thousand Islands There Are A Total Of N Islands In Maldives Numbe 1 (47.1 KiB) Viewed 41 times

Task 4 Dalai Lama is visiting Maldives, the land of a thousand islands. There are a total of N islands in Maldives numbered from 1 to N. All pairs of islands are connected to each other by bidirectional bridges running over water. Given Dalai Lama's health condition, crossing these bridges requires a lot of effort. He is standing at Island #1 and wants to reach the Island #N, where he will attend a ceremony where leaders of all countries are gathered to celebrate his life and achievements. Find the minimum number of bridges that Dalai Lama shall have to cross, if he takes the optimal route. 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 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 Sample Input: 2 32 724 12 23 234 44 123+ 12 2342 23 34 522 42 #there are 2 graphs in the test case (text file) #3 indicates that the first graph contains 3 vertices. 2 indicates the number of edges/connections # - there is a connection between vertex 1 and 2 Sample Output: 2 2 #- there is a connection between vertex 2 and 3 #-4 indicates that the second graph contains 4 vertices. 4 indicates the number of edges/connections #- there is a connection between vertex 1 and 2 #- there is a connection between vertex 2 and 3 #- there is a connection between vertex 3 and 4 #- there is a connection between vertex 4 and 2