Submission #1690112

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
int level[200005];
int v[200005];
int main(){
	int n,m;
	cin >> n >> m;
	vector<int> g[200005];
	while(m--){
		int a,b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	memset(level,-1,sizeof(level));
	level[1] = 0;
	queue<int> q;
	q.push(1);

	while(q.size()){
		int u=q.front();
		q.pop();
		if(!v[u]){
			v[u] = true;
			for(int i=0;i<g[u].size();++i){
				int r = g[u][i];
				if(!v[r]){
					q.push(r);
					level[r] = level[u] +1;
				}
			}
		}
	}
	if(level[n]==2)cout << "POSSIBLE\n";
	else cout << "IMPOSSIBLE\n";
}

Submission Info

Judge Result