stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define range(i, a, b) for(int i = (a); i < (b); i++)

#define rep(i, a) range(i, 0, a)

using namespace std;

int d, n;

vector <int> a, e, r;

vector <vector <int>> memo;

const int INF = 1000000000;



void rec(int c = 0, int exp = 0, int end = d) {

	if (memo[exp][end] <= c) return;

	memo[exp][end] = c;



	rep (i, n) {

		if (exp < r[i]) continue;

		rec(c + 1, min(exp + e[i], 100), max(end - a[i], 0));

	}

}



int main() {

	while (cin >> d >> n, d) {

		a = e = r = vector <int> (n);

		rep (i, n) cin >> a[i] >> e[i] >> r[i];

		memo = vector <vector <int>> (105, vector <int> (105, INF));

		rec();

		int ans = INF;

		rep (i, 101) ans = min(ans, memo[i][0]);

		cout << (ans == INF ? "NA" : to_string(ans)) << endl;

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1271980551498995x):
#include <bits/stdc++.h>

#define range(i, a, b) for(int i = (a); i < (b); i++)

#define rep(i, a) range(i, 0, a)

using namespace std;

const int INF = 1000000000;



int main() {

	int d, n;

	while (cin >> d >> n, d) {

		int a[n], e[n], r[n];

		rep (i, n) cin >> a[i] >> e[i] >> r[i];

		//耐久値、経験値

		int dp[d + 1][101];

		rep (i, d + 1) rep (j, 101) dp[i][j] = INF;

		dp[d][0] = 0;

		for (int i = d; i >= 0; i--) rep (j, 101) {

			if (dp[i][j] == INF) continue;

			rep (k, n) {

				if (r[k] > j) continue;

				//a[i] -> 減る耐久値, e[i] -> 得る経験値

				dp[max(0, i - a[k])][min(100, j + e[k])] = min(dp[max(0, i - a[k])][min(100, j + e[k])],

																											 dp[i][j] + 1);

			}

		}

		int ans = INF;

		rep (i, 101) ans = min(ans, dp[0][i]);

		cout << (ans == INF ? "NA" : to_string(ans)) << endl;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

using namespace std;

int D, N, a[111], e[111], r[111], dp[111][111];

int main() {

	while (cin >> D >> N, D | N) {

		for (int i = 0; i < N; i++) cin >> a[i] >> e[i] >> r[i];

		int maxr = *max_element(r, r + N);

		for (int i = 0; i <= D; i++) fill(dp[i], dp[i] + maxr + 1, 999999999);

		dp[0][0] = 0;

		for (int i = 0; i < D; i++) {

			for (int j = 0; j <= maxr; j++) {

				for (int k = 0; k < N; k++) {

					if (j < r[k]) continue;

					int p = min(j + e[k], maxr), q = min(i + a[k], D);

					dp[q][p] = min(dp[q][p], dp[i][j] + 1);

				}

			}

		}

		int ret = *min_element(dp[D], dp[D] + maxr + 1);

		if (ret == 999999999) cout << "NA" << endl;

		else cout << ret << endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 4.616715179912416x):
#include <cstdio>

#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

int D, N, a[111], e[111], r[111], dp[111][111];

int main() {

	while (scanf("%d%d", &D, &N), D | N) {

		for (int i = 0; i < N; i++) scanf("%d%d%d", a + i, e + i, r + i);

		int maxr = *max_element(r, r + N);

		for (int i = 0; i <= D; i++) fill(dp[i], dp[i] + maxr + 1, 999999999);

		dp[0][0] = 0;

		for (int i = 0; i < D; i++) {

			for (int j = 0; j <= maxr; j++) {

				for (int k = 0; k < N; k++) {

					if (j < r[k]) continue;

					int p = min(j + e[k], maxr), q = min(i + a[k], D);

					dp[q][p] = min(dp[q][p], dp[i][j] + 1);

				}

			}

		}

		int ret = *min_element(dp[D], dp[D] + maxr + 1);

		if (ret == 999999999) puts("NA");

		else printf("%d\n", ret);

	}

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

using namespace std;

int D, N, a[111], e[111], r[111], dp[111][111];

int main() {

	while (cin >> D >> N, D | N) {

		for (int i = 0; i < N; i++) cin >> a[i] >> e[i] >> r[i];

		int maxr = *max_element(r, r + N);

		for (int i = 0; i <= D; i++) fill(dp[i], dp[i] + maxr + 1, 999999999);

		dp[0][0] = 0;

		for (int i = 0; i < D; i++) {

			for (int j = 0; j <= maxr; j++) {

				for (int k = 0; k < N; k++) {

					if (j < r[k]) continue;

					int p = min(j + e[k], maxr), q = min(i + a[k], D);

					dp[q][p] = min(dp[q][p], dp[i][j] + 1);

				}

			}

		}

		int ret = *min_element(dp[D], dp[D] + maxr + 1);

		if (ret == 999999999) cout << "NA" << endl;

		else cout << ret << endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 4.616715179912416x):
#include <cstdio>

#include <algorithm>

using namespace std;

int D, N, a[111], e[111], r[111], dp[111][111];

int main() {

	while (scanf("%d%d", &D, &N), D | N) {

		for (int i = 0; i < N; i++) scanf("%d%d%d", a + i, e + i, r + i);

		int maxr = *max_element(r, r + N);

		for (int i = 0; i <= D; i++) fill(dp[i], dp[i] + maxr + 1, 999999999);

		dp[0][0] = 0;

		for (int i = 0; i < D; i++) {

			for (int j = 0; j <= maxr; j++) {

				for (int k = 0; k < N; k++) {

					if (j < r[k]) continue;

					int p = min(j + e[k], maxr), q = min(i + a[k], D);

					dp[q][p] = min(dp[q][p], dp[i][j] + 1);

				}

			}

		}

		int ret = *min_element(dp[D], dp[D] + maxr + 1);

		if (ret == 999999999) puts("NA");

		else printf("%d\n", ret);

	}

}
// Slower C++ solution:
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>

using namespace std;



#define rep(i, n) REP(i, 0, n)

#define ALL(v) v.begin(), v.end()

#define MSG(a) cout << #a << " " << a << endl;

#define REP(i, x, n) for (int i = x; i < n; i++)

#define OP(m) cout << m << endl

typedef long long ll;

typedef unsigned long long ull;



vector<int> g[200000];



int main()

{

    int n, m;

    cin >> n >> m;

    rep(i, m)

    {

        int a, b;

        cin >> a >> b;

        --a, --b;

        g[a].push_back(b);

        g[b].push_back(a);

    }

    int flag = 0;

    rep(i, g[0].size())

    {

        int v = g[0][i];

        if (find(ALL(g[v]), n - 1) != g[v].end())

            flag = 1;

    }

    flag == 1 ? OP("POSSIBLE") : OP("IMPOSSIBLE");



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.474412333583543x):
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>

using namespace std;



#define rep(i, n) REP(i, 0, n)

#define ALL(v) v.begin(), v.end()

#define MSG(a) cout << #a << " " << a << endl;

#define REP(i, x, n) for (int i = x; i < n; i++)

#define OP(m) cout << m << endl

typedef long long ll;

typedef unsigned long long ull;



int main()

{

    int n, m;

    cin >> n >> m;



    bool a[n] = {}, b[n] = {};



    rep(i, m)

    {

        int to, from;

        cin >> to >> from;

        to--, from--;

        if (to == 0)

            a[from] = 1;

        if (from == n - 1)

            b[to] = 1;

    }



    rep(i, n)

    {

        if (a[i] == 1 && b[i] == 1)

        {

            OP("POSSIBLE");

            return 0;

        }

    }



    OP("IMPOSSIBLE");



    return 0;

}



/*vector<int> g[200000];



int main()

{

    int n, m;

    cin >> n >> m;

    rep(i, m)

    {

        int a, b;

        cin >> a >> b;

        --a, --b;

        g[a].push_back(b);

        g[b].push_back(a);

    }

    int flag = 0;

    rep(i, g[0].size())

    {

        int v = g[0][i];

        if (find(ALL(g[v]), n - 1) != g[v].end())

            flag = 1;

    }

    flag == 1 ? OP("POSSIBLE") : OP("IMPOSSIBLE");



    return 0;

}*/
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 100020

#define ll long long

using namespace std;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());

	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return f?x:-x;

}

std::map<int, bool> to1, to2;

int main(int argc, char const *argv[]) {

	int n = read(), m = read();

	while (m --) {

		int x = read(), y = read();

		if (x > y) swap(x, y);

		if (x == 1) to2[y] = 1;

		if (y == n) to1[x] = 1;

	}

	for (int i = 2; i < n; i++)

		if (to1[i] && to2[i])

			return puts("POSSIBLE")&0;

	puts("IMPOSSIBLE");

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.352566874652499x):
#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<map>

#include<cstring>

#include<algorithm>

#define ll long long

#define Max(x,y) ((x) > (y) ? (x) : (y))

#define Min(x,y) ((x) < (y) ? (x) : (y))

#define mod 1000000007

#define N 200010

using namespace std;

inline int read(){

	int x = 0,f = 1;char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}

	while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}

	return x*f;

}



int n,m;

int nxt[N*2],to[N*2],head[N],cnt;



void add(int x,int y){

	to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt;

	to[++cnt] = x; nxt[cnt] = head[y]; head[y] = cnt;

}



int main(){

	n = read(); m = read();

	for(int i = 1;i <= m;i++){

		int x = read(),y = read();

		add(x,y);

	}

	for(int i = head[1];i;i = nxt[i]){

		if(to[i] == n){

			puts("POSSIBLE");

			return 0;

		}

		for(int j = head[to[i]];j;j = nxt[j]){

			if(to[j] == n){

				puts("POSSIBLE");

				return 0;

			}

		}

	}

	puts("IMPOSSIBLE");

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

const int N=200005;

int n,m,x,y;

bool b[N],c[N];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d%d",&x,&y);

		if(x==1)b[y]=true;

		if(y==n)c[x]=true;

	}

	c[1]=true;

	b[n]=true;

	for(int i=1;i<=n;i++)

		if(b[i]&&c[i]){

			puts("POSSIBLE");

			return 0;

		}

	puts("IMPOSSIBLE");

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.30907217022995x):
#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<map>

#include<cstring>

#include<algorithm>

#define ll long long

#define Max(x,y) ((x) > (y) ? (x) : (y))

#define Min(x,y) ((x) < (y) ? (x) : (y))

#define mod 1000000007

#define N 200010

using namespace std;

inline int read(){

	int x = 0,f = 1;char ch = getchar();

	while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}

	while(ch >= '0' && ch <= '9'){x = x*10+ch-'0';ch = getchar();}

	return x*f;

}



int n,m;

int nxt[N*2],to[N*2],head[N],cnt;



void add(int x,int y){

	to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt;

	to[++cnt] = x; nxt[cnt] = head[y]; head[y] = cnt;

}



int main(){

	n = read(); m = read();

	for(int i = 1;i <= m;i++){

		int x = read(),y = read();

		add(x,y);

	}

	for(int i = head[1];i;i = nxt[i]){

		if(to[i] == n){

			puts("POSSIBLE");

			return 0;

		}

		for(int j = head[to[i]];j;j = nxt[j]){

			if(to[j] == n){

				puts("POSSIBLE");

				return 0;

			}

		}

	}

	puts("IMPOSSIBLE");

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define ll long long

#define N 200005

#define mod 1000000007

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }

	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

	return x*f;

}

map<ll,ll>mp[N];

ll n,m;

int main(){

	n=read(); m=read();

	rep(i,1,m){

		ll u=read(),v=read();

		mp[u][v]=1; mp[v][u]=1;

	}

	rep(i,2,n-1) if (mp[1][i]&&mp[i][n]) return puts("POSSIBLE")&0;

	puts("IMPOSSIBLE");

}

// Faster C++ solution for the same problem (measured speedup: 2.356809981769451x):
#include<bits/stdc++.h>

using namespace std;

int read(){

	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();

	int kk=1,k=0;if (c=='-')kk=-1,c=getchar();

	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;

}int n,m,f[1000000],x,y;

struct lsg{int x,y;}a[1000000];

int pd(lsg x,lsg y){return x.y<y.y;}

int main(){

	n=read();m=read();memset(f,10,sizeof(f));f[1]=0;

	for (int i=1;i<=m;i++){

		x=read();y=read();

		a[i].x=x;a[i].y=y;

	}sort(a+1,a+1+m,pd);

	for (int i=1;i<=m;i++)f[a[i].y]=min(f[a[i].x]+1,f[a[i].y]);

	if (f[n]<=2)puts("POSSIBLE");else puts("IMPOSSIBLE");

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define ll long long

#define N 200005

#define mod 1000000007

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }

	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

	return x*f;

}

map<ll,ll>mp[N];

ll n,m;

int main(){

	n=read(); m=read();

	rep(i,1,m){

		ll u=read(),v=read();

		mp[u][v]=1; mp[v][u]=1;

	}

	rep(i,2,n-1) if (mp[1][i]&&mp[i][n]) return puts("POSSIBLE")&0;

	puts("IMPOSSIBLE");

}

// Faster C++ solution for the same problem (measured speedup: 12.118360398240576x):
#include<bits/stdc++.h>

using namespace std;

struct edge{

	int to,next;

}e[400010];

int head[200010];

int n,m,nedge;

 inline void add(int a,int b)

{

	e[++nedge].to=b;

	e[nedge].next=head[a];

	head[a]=nedge;

}



 int main()

{

	scanf("%d%d",&n,&m);

	for (int i=1;i<=m;++i)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		add(u,v);add(v,u);

	}

	for (int i=2;i<=n-1;++i)

	{

		bool f1=0,f2=0;

		for (int k=head[i];k;k=e[k].next)

		{

			if (e[k].to==1) f1=1;

			if (e[k].to==n) f2=1;

		}

		if (f1&&f2)

		{

			puts("POSSIBLE");

			return 0;

		}

	}

	puts("IMPOSSIBLE");

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int read(){

	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();

	int kk=1,k=0;if (c=='-')kk=-1,c=getchar();

	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;

}int n,m,f[1000000],x,y;

struct lsg{int x,y;}a[1000000];

int pd(lsg x,lsg y){return x.y<y.y;}

int main(){

	n=read();m=read();memset(f,10,sizeof(f));f[1]=0;

	for (int i=1;i<=m;i++){

		x=read();y=read();

		a[i].x=x;a[i].y=y;

	}sort(a+1,a+1+m,pd);

	for (int i=1;i<=m;i++)f[a[i].y]=min(f[a[i].x]+1,f[a[i].y]);

	if (f[n]<=2)puts("POSSIBLE");else puts("IMPOSSIBLE");

}


// Faster C++ solution for the same problem (measured speedup: 5.14184872432623x):
#include<bits/stdc++.h>

using namespace std;

struct edge{

	int to,next;

}e[400010];

int head[200010];

int n,m,nedge;

 inline void add(int a,int b)

{

	e[++nedge].to=b;

	e[nedge].next=head[a];

	head[a]=nedge;

}



 int main()

{

	scanf("%d%d",&n,&m);

	for (int i=1;i<=m;++i)

	{

		int u,v;

		scanf("%d%d",&u,&v);

		add(u,v);add(v,u);

	}

	for (int i=2;i<=n-1;++i)

	{

		bool f1=0,f2=0;

		for (int k=head[i];k;k=e[k].next)

		{

			if (e[k].to==1) f1=1;

			if (e[k].to==n) f2=1;

		}

		if (f1&&f2)

		{

			puts("POSSIBLE");

			return 0;

		}

	}

	puts("IMPOSSIBLE");

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define ll long long

#define N 200005

#define mod 1000000007

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }

	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

	return x*f;

}

map<ll,ll>mp[N];

ll n,m;

int main(){

	n=read(); m=read();

	rep(i,1,m){

		ll u=read(),v=read();

		mp[u][v]=1; mp[v][u]=1;

	}

	rep(i,2,n-1) if (mp[1][i]&&mp[i][n]) return puts("POSSIBLE")&0;

	puts("IMPOSSIBLE");

}

// Faster C++ solution for the same problem (measured speedup: 12.150830928042776x):
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<math.h>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<set>

#include<vector>

#include<bitset>

#include<map>

#define N 200005

#define ll long long

#define oo 100000000

#define For(i,x,y) for(int i=x;i<=y;i++)

#define Rep(i,x,y) for(int i=x;i>=y;i--)

#define Forn(i,x,y) for(int i=x;i<y;i++)

using namespace std;

inline int read(){int x=0,f=0;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-48;return f?-x:x;}

inline void write(ll x){if(x<10) putchar(x+48);else write(x/10),putchar(x%10+48);}

inline void writeln(ll x){if(x<0) putchar('-'),x=-x;write(x);putchar('\n');}

int n,m,st[N],ed[N];

int main(){

	n=read();m=read();

	For(i,1,m){

		int x=read(),y=read();

		if(x>y) swap(x,y);

		if(x==1) st[y]=1;

		if(y==n) ed[x]=1;

	}

	For(i,1,n) if(st[i]&&ed[i]){puts("POSSIBLE");return 0;}

	puts("IMPOSSIBLE");

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int read(){

	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();

	int kk=1,k=0;if (c=='-')kk=-1,c=getchar();

	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;

}int n,m,f[1000000],x,y;

struct lsg{int x,y;}a[1000000];

int pd(lsg x,lsg y){return x.y<y.y;}

int main(){

	n=read();m=read();memset(f,10,sizeof(f));f[1]=0;

	for (int i=1;i<=m;i++){

		x=read();y=read();

		a[i].x=x;a[i].y=y;

	}sort(a+1,a+1+m,pd);

	for (int i=1;i<=m;i++)f[a[i].y]=min(f[a[i].x]+1,f[a[i].y]);

	if (f[n]<=2)puts("POSSIBLE");else puts("IMPOSSIBLE");

}


// Faster C++ solution for the same problem (measured speedup: 5.155626046237359x):
#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<math.h>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<set>

#include<vector>

#include<bitset>

#include<map>

#define N 200005

#define ll long long

#define oo 100000000

#define For(i,x,y) for(int i=x;i<=y;i++)

#define Rep(i,x,y) for(int i=x;i>=y;i--)

#define Forn(i,x,y) for(int i=x;i<y;i++)

using namespace std;

inline int read(){int x=0,f=0;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-48;return f?-x:x;}

inline void write(ll x){if(x<10) putchar(x+48);else write(x/10),putchar(x%10+48);}

inline void writeln(ll x){if(x<0) putchar('-'),x=-x;write(x);putchar('\n');}

int n,m,st[N],ed[N];

int main(){

	n=read();m=read();

	For(i,1,m){

		int x=read(),y=read();

		if(x>y) swap(x,y);

		if(x==1) st[y]=1;

		if(y==n) ed[x]=1;

	}

	For(i,1,n) if(st[i]&&ed[i]){puts("POSSIBLE");return 0;}

	puts("IMPOSSIBLE");

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define ll long long

#define N 200005

#define mod 1000000007

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }

	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

	return x*f;

}

map<ll,ll>mp[N];

ll n,m;

int main(){

	n=read(); m=read();

	rep(i,1,m){

		ll u=read(),v=read();

		mp[u][v]=1; mp[v][u]=1;

	}

	rep(i,2,n-1) if (mp[1][i]&&mp[i][n]) return puts("POSSIBLE")&0;

	puts("IMPOSSIBLE");

}

// Faster C++ solution for the same problem (measured speedup: 11.943004990031964x):




#include <algorithm>

#include <iostream>

#include <sstream>

#include <iomanip>

#include <vector>

#include <string>

#include <string.h>

#include <cstdio>

#include <bitset>

#include <cmath>

#include <map>

#include <set>

#include <fstream>

#define maxn 2000000



using namespace std;

int a, b;

struct pp

{

	int a, b;

}po[maxn];

bool cmp(pp x, pp y)

{

	if (x.a == y.a)

		return x.b > y.b;

	else

		return x.a < y.a;

}

int main()

{

	int n = 0, m = 0;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)

	{

		cin >> a >> b;

		po[i].a = a; po[i].b = b;

	}

	sort(po, po + m, cmp);

	int f = 0, i = 0;

	while (1)

	{

		if (po[i++].a == 1)

		{



			int l = i - 1, r = n, mid = 0, pos = -1;

			while (l <= r)

			{

				mid = (l + r) / 2;

				if (po[mid].a > po[i - 1].b)

					r = mid - 1;

				else if (po[mid].a == po[i - 1].b)

				{

					pos = mid;

					break;

				}

				else

					l = mid + 1;



			}

			if (pos == -1 || pos >= m) continue;

			if (po[pos].b == n)

			{

				cout << "POSSIBLE" << endl;

				break;

			}

			else

				continue;

		}

		else if (i - 1 >= m)

		{

			cout << "IMPOSSIBLE" << endl;

			break;

		}

		else if (i - 1 < m&&po[i - 1].a > 1)

		{

			cout << "IMPOSSIBLE" << endl;

			break;

		}

	}

	//system("pause");

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int read(){

	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();

	int kk=1,k=0;if (c=='-')kk=-1,c=getchar();

	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;

}int n,m,f[1000000],x,y;

struct lsg{int x,y;}a[1000000];

int pd(lsg x,lsg y){return x.y<y.y;}

int main(){

	n=read();m=read();memset(f,10,sizeof(f));f[1]=0;

	for (int i=1;i<=m;i++){

		x=read();y=read();

		a[i].x=x;a[i].y=y;

	}sort(a+1,a+1+m,pd);

	for (int i=1;i<=m;i++)f[a[i].y]=min(f[a[i].x]+1,f[a[i].y]);

	if (f[n]<=2)puts("POSSIBLE");else puts("IMPOSSIBLE");

}


// Faster C++ solution for the same problem (measured speedup: 5.067445013562515x):




#include <algorithm>

#include <iostream>

#include <sstream>

#include <iomanip>

#include <vector>

#include <string>

#include <string.h>

#include <cstdio>

#include <bitset>

#include <cmath>

#include <map>

#include <set>

#include <fstream>

#define maxn 2000000



using namespace std;

int a, b;

struct pp

{

	int a, b;

}po[maxn];

bool cmp(pp x, pp y)

{

	if (x.a == y.a)

		return x.b > y.b;

	else

		return x.a < y.a;

}

int main()

{

	int n = 0, m = 0;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)

	{

		cin >> a >> b;

		po[i].a = a; po[i].b = b;

	}

	sort(po, po + m, cmp);

	int f = 0, i = 0;

	while (1)

	{

		if (po[i++].a == 1)

		{



			int l = i - 1, r = n, mid = 0, pos = -1;

			while (l <= r)

			{

				mid = (l + r) / 2;

				if (po[mid].a > po[i - 1].b)

					r = mid - 1;

				else if (po[mid].a == po[i - 1].b)

				{

					pos = mid;

					break;

				}

				else

					l = mid + 1;



			}

			if (pos == -1 || pos >= m) continue;

			if (po[pos].b == n)

			{

				cout << "POSSIBLE" << endl;

				break;

			}

			else

				continue;

		}

		else if (i - 1 >= m)

		{

			cout << "IMPOSSIBLE" << endl;

			break;

		}

		else if (i - 1 < m&&po[i - 1].a > 1)

		{

			cout << "IMPOSSIBLE" << endl;

			break;

		}

	}

	//system("pause");

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define ll long long

#define N 200005

#define mod 1000000007

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }

	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

	return x*f;

}

map<ll,ll>mp[N];

ll n,m;

int main(){

	n=read(); m=read();

	rep(i,1,m){

		ll u=read(),v=read();

		mp[u][v]=1; mp[v][u]=1;

	}

	rep(i,2,n-1) if (mp[1][i]&&mp[i][n]) return puts("POSSIBLE")&0;

	puts("IMPOSSIBLE");

}

// Faster C++ solution for the same problem (measured speedup: 11.677775249294198x):
#include <bits/stdc++.h>

#define FOR(k,m,n) for(int(k)=(m);(k)<(n);(k)++)

#define REP(k,n) FOR((k),0,(n))

using namespace std;

typedef long long ll;

typedef vector<ll> VLL;

const int MOD=1000000007;



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);



    ll n, m;

    cin >> n >> m;



    vector< vector<ll> > arr(n);



    ll a, b;

    REP(i, m){

        cin >> a >> b;

        a--;

        b--;

        arr[a].push_back(b);

        arr[b].push_back(a);

    }



    REP(i, arr[0].size()){

        REP(j, arr[arr[0][i]].size()){

            if(arr[arr[0][i]][j] == n-1){

                cout << "POSSIBLE" << endl;

                return 0;

            }

        }

    }



    cout << "IMPOSSIBLE" << endl;



    return 0;

}