Submission #2558750

---

Source Code Expand

#include <cstdio>
using namespace std;

const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
struct E {int v, nt;} e[N<<1];
int n, m, tot, h[N], q[N], inq[N], boats[N];

inline void add(int u, int v) {e[++tot] = (E){v, h[u]}, h[u] = tot;}
template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline int bfs(int s, int t) {
	int i, u, v, l = 0, r = 0;
	for (inq[q[++r] = s] = 1; l < r;) {
		if (boats[u = q[++l]] > 2) continue;
		for (i = h[u]; i; i = e[i].nt)
			if (!inq[v = e[i].v]) inq[v] = 1, boats[q[++r] = v] = boats[u] + 1;
	}
	return inq[t];
}

inline void work() {
	int u, v; in(n), in(m);
	for (int i = 1; i <= m; ++i) in(u), in(v), add(u, v);
	if (bfs(1, n)) puts("POSSIBLE");
	else puts("IMPOSSIBLE");
}

int main() {work(); return 0;}

Submission Info

Judge Result