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:
23 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;
int vis;int dist;

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;

}
}```

darkmode