# Monk and the Islands HackerEarth Solution and Explanation

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 TT testcases follow.
First line of each test case contains two space-separated integers NM.
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, YN

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

```2
2```

## Solution in c++

```#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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();

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;