Monk and the Islands

 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 efforts. He is standing at Island #1 and wants to reach the Island #N. Find the minimum the number of bridges that he shall have to cross, if he takes the optimal route.

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


Output: 
2
2

c++ implementation:

#include <bits/stdc++.h>
using namespace std;

vector<int> ar[10001];
int vis[10001];int dist[10001];

void bfs(int s)
{
	queue<int>q;
	q.push(s);
	vis[s]=1;
	dist[s]=0;

	while(!q.empty())
	{
		int c=q.front();
		q.pop();

		for(auto x:ar[c])
		{
			if(vis[x]==0)
			{
				q.push(x);
			    dist[x]=dist[c]+1;
				vis[x]=1;
			}
		}

	}
}


int main() {
	int t;
	cin >> t;										
	while(t--)
	{
		int n,m;
                cin>>n>>m; 
         
		 for(int i=0;i<=n;i++)
		 {
			 ar[i].clear();
			 vis[i]=0;
			 dist[i]=0;
		 }

		 

		 while(m--)
		 {
			 int a,b;
			 cin>>a>>b;
                         ar[a].push_back(b);
			 ar[b].push_back(a);
		 }
                bfs(1);
		 cout<<dist[n]<<endl;

	}		
}