# 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; } }