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 effort. He is standing at Island #1 and wants to reach the Island #N. Find the minimum 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** ≤ 10^{4}

1 ≤ **M** ≤ 10^{5}

1 ≤ **X**, **Y** ≤ **N**

## Sample Input:

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

## Sample Output:

2 2

## Solution in c++

#include <iostream> #include <bits/stdc++.h> using namespace std; vector <int> adj[1000000]; int dist[10001], visted[100000]; void BFS(int src){ queue <int> q; q.push(src); visted[src] = 1; dist[src] = 0; // While loop till queue became empty i.e BFS Operation while(!q.empty()) { // store the value of first element of queue into current node value int current = q.front(); q.pop(); for(int child: adj[current]){ if(visted[child] ==0){ q.push(child); dist[child] = dist[current] + 1; visted[child] = 1; } } } } int main(){ int t,N,M,X,Y; cin>>t; while(t--){ cin>>N>>M; for(int i =1;i<=N;i++) adj[i].clear(), visted[i] = 0; for(int i = 0;i<M;i++){ cin>>X>>Y; adj[X].push_back(Y); adj[Y].push_back(X); } BFS(1); cout<<dist[N]<<endl; } }

You must be logged in to post a comment.