Problem:
 Score : 300 points    Problem Statement In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1 , Island 2 , ..., Island N .  There are M kinds of regular boat services between these islands.
Each service connects two islands. The i -th service connects Island a_i and Island b_i .  Cat Snuke is on Island 1 now, and wants to go to Island N .
However, it turned out that there is no boat service from Island 1 to Island N , so he wants to know whether it is possible to go to Island N by using two boat services.  Help him.      Constraints  3 ≤ N ≤ 200  000  1 ≤ M ≤ 200  000  1 ≤ a_i < b_i ≤ N  (a_i, b_i) \neq (1, N)  If i \neq j , (a_i, b_i) \neq (a_j, b_j) .         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2 : a_M  b_M       Output If it is possible to go to Island N by using two boat services, print POSSIBLE ; otherwise, print IMPOSSIBLE .        Sample Input 1 3 2
1 2
2 3      Sample Output 1 POSSIBLE       Sample Input 2 4 3
1 2
2 3
3 4      Sample Output 2 IMPOSSIBLE  You have to use three boat services to get to Island 4 .       Sample Input 3 100000 1
1 99999      Sample Output 3 IMPOSSIBLE       Sample Input 4 5 5
1 3
4 5
2 3
2 4
1 4      Sample Output 4 POSSIBLE  You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5 .

Solution (Python):
n, m = [int(_) for _ in input().split()]
dict = {}
can = True
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    if a in dict.keys():
        dict[a].append(b)
    else:
        dict[a] = [b]
if not 1 in dict.keys():
    can = False
else:
    for i in dict[1]:
        if i in dict.keys() and n in dict[i]:
            can = True
            break
        else:
            can = False
print('POSSIBLE' if can else 'IMPOSSIBLE')

Solution (Python):
def main():
    n, m = map(int, input().split())
    Ton, Fr1 = set(), set()
    for _ in range(m):
        a, b = map(int, input().split())
        if b==n:
            Ton.add(a)
        if a==1:
            Fr1.add(b)

    print('POSSIBLE' if Ton&Fr1 else 'IMPOSSIBLE')

main()

Solution (Python):
n, m = map(int, input().split())
ab = {}
for _ in range(m):
    a_, b_ = map(str, input().split())
    ab.setdefault(a_, []).append(b_)
r = "IMPOSSIBLE"
if "1" in ab.keys():
    for i in ab["1"]:
        if i not in ab.keys():
            continue
        if str(n) in ab[i]:
            r = "POSSIBLE"
            break
print(r)

Solution (Python):
N, M = map(int, input().split())
edges = [[] for i in range(N)]
 
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    

for i in edges[1]:
    
    if N in edges[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

r = [[] for _ in range(n)]
for a, b in ab:
    r[a-1].append(b-1)
    r[b-1].append(a-1)

for i in r[0]:
    if n-1 in r[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

for g in G:
    island_1=False
    island_n=False
    for gg in g:
        if gg==0:
            island_1=True
        if gg==n-1:
            island_n=True
    if island_1==True and island_n==True: 
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
edges = [[] for i in range(N)]

for i in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)

for i in edges[1]:
  if N in edges[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
edges = [[] for i in range(N)]

for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  edges[a].append(b)

for i in edges[0]:
  if N-1 in edges[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    if not len(x)+len(y)==len(set(x+y)):
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    if not len(x)+len(y)==len(set(x+y)):
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]

cont_1 = set()
cont_n = set()

for ab in AB:
  a, b = ab
  if 1 in ab:
    cont_1.add(a)
    cont_1.add(b)
  if n in ab:
    cont_n.add(a)
    cont_n.add(b)

if cont_1 & cont_n:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
you=[]
other={i:False for i in range(n+1)}
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        you.append(b)
    elif b==n:
        other[a]=True
flag=False
for some in you:
    if other[some]:
        flag=True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int,input().split())
data = [list(map(int, input().split())) for _ in range(m)]
start = set(i[1] for i in data if i[0] == 1)
goal = set(j[0] for j in data if j[1] == n)

if start & goal:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
sa=set()
sb=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
      sb.add(b)
    if b==N:
      sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=[0]*N
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        if a==0 or b==0:
            S[a+b]+=1
        if a==N-1 or b==N-1:
            S[a+b-(N-1)]+=1
            
    f=0
    for i in range(N):
        if S[i]==2:
            f=1
            
    if f==1:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
        

main()

Solution (Python):

n,m=map(int,input().split())
s1=set()
sn=set()
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        s1.add(b)
    if b==n:
        sn.add(a)
print('POSSIBLE' if len(s1&sn) else 'IMPOSSIBLE')

Solution (Python):
def solve():
    N, M, *AB = map(int, open(0).read().split())
    FROM_1 = set()
    TO_N = set()
    for i in range(M):
        a, b = AB[2*i], AB[2*i + 1]
        if a == 1:
            FROM_1.add(b)
        elif a == N:
            TO_N.add(b)
        if b == 1:
            FROM_1.add(a)
        elif b == N:
            TO_N.add(a)
    ans = FROM_1 & TO_N
    print('POSSIBLE') if ans else print('IMPOSSIBLE')

if __name__ == '__main__':
   solve()

Solution (Python):
n, m = map(int,input().split())
ab = [0 for _ in range(n+2)]

for _ in range(m):
    a, b = map(int, input().split())
    if a==1:
        ab[b] += 1
        continue
    elif b == n:
        ab[a] += 1
        continue
if max(ab) == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
to_c = []
fm_c = []

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        to_c.append(b)
    if b == n:
        fm_c.append(a)

if len(set(to_c) & set(fm_c)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = list(map(int,input().split()))
lst = [set() for i in range(N+1)]
for i in range(M):
    a,b = list(map(int,input().split()))
    lst[a].add(b)

for intermediate in lst[1]:
    if N in lst[intermediate]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split(" "))
x = set()
y = set()
for i in range(m):
  a,b =  map(int,input().split(" "))
  if(a==1):
    x.add(b)
  if(b==n):
    y.add(a)

x = x.intersection(y)

if len(x)!=0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
def solve():
    N, M = map(int, input().split())
    FROM_1 = set()
    TO_N = set()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            FROM_1.add(b)
        elif a == N:
            TO_N.add(b)
        if b == 1:
            FROM_1.add(a)
        elif b == N:
            TO_N.add(a)
    ans = FROM_1 & TO_N
    print('POSSIBLE') if ans else print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    FROM_1 = set()
    TO_N = set()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            FROM_1.add(b)
        elif a == N:
            TO_N.add(b)
        if b == 1:
            FROM_1.add(a)
        elif b == N:
            TO_N.add(a)
    ans = FROM_1 & TO_N
    print('POSSIBLE') if ans else print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    N, M = map(int, input().split())
    T = {}
    for i in range(M):
        a, b = map(int, input().split())
        if a not in T:
            T[a] = []
        T[a].append(b)
        if b not in T:
            T[b] = []
        T[b].append(a)
    
    FROM_1 = T[1]

    for f in FROM_1:
        if N in T[f]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Solution (Python):
N, M = map(int, input().split())
T = {}
for i in range(M):
    a, b = map(int, input().split())
    if a not in T:
        T[a] = []
    T[a].append(b)
    if b not in T:
        T[b] = []
    T[b].append(a)

FROM_1 = T[1]

for f in FROM_1:
    if N in T[f]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
n, m = [int(i) for i in input().split()]
p = [[int(i) for i in input().split()] for _ in range(m)]
a = []
for x in p:
    if x[0] == 1:
        a.append(x[1])

b = []
for x in p:
    if x[1] == n:
        b.append(x[0])
if set(a) & set(b):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
l=[[0,0]]*m
at=[0]*m
bt=[0]*m
atc=0
btc=0
a=False

f=0
for k in range(m):
  ln=list(map(int,input().split()))
  if ln[0]==1:
    at[atc]=ln[1]
    atc+=1
  elif ln[1]==n:
    bt[btc]=ln[0]
    btc+=1
del at[atc:]
del bt[btc:]
at.sort()
bt.sort()
c=list(set(at)^set(bt))
if len(c)!=(atc+btc):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m =map(int,input().split())
s = []
e = []
for i in range(m):
    a,b = map(int,input().split())
    if a ==1:
        s.append(b)
    if b == n:
        e.append(a)
if set(s)&set(e):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())

one2 = set()
toN = set()

for _ in range(M):
    a, b = map(int, input().split())

    if a == 1:
        one2.add(b)

    if b == N:
        toN.add(a)

inter = one2 & toN

if len(inter) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())

A = []
B = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
    if b == n:
        B.append(a)

if len(set(A) & set(B)) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


if __name__ == "__main__":
    n, m = map(int, input().split())

    g1 = Graph()

    for i in range(m):
        a, b = map(int, input().split())
        g1.add_edge(a-1, b-1)
        g1.add_edge(b-1, a-1)

    d = Dijkstra(g1, 0)

    if d.dist[n-1] == 2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
a,b=[0]*m,[0]*m
c=[False]*(n+1)
d=[False]*(n+1)
for i in range(m):
    a[i],b[i] = map(int,input().split())
    if a[i]==1: c[b[i]]=True
    if b[i]==n: d[a[i]]=True
for i in range(n):
    if c[i] and d[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())

E = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def bfs(cur, pre, d):
    stack = deque([[cur, pre, d]])
    while stack:
        cur, pre, d = stack.popleft()
        if cur == n-1:
            return True
        for e in E[cur]:
            if e != pre and d < 2:
                stack.append([e, cur, d+1])
    return False

if bfs(0, -1, 0):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())

edges=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
def dfs(cnt,v,before=-1):
    if cnt>=2:
        return False
    ans=False
    for to in edges[v]:
        if to!=before:
            if to==n-1:
                return True
            else:
                ans|=dfs(cnt+1,to,v)
    return ans

if dfs(0,0):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = [int(i) for i in input().split()]
p = [[int(i) for i in input().split()] for _ in range(m)]
a = []
for x in p:
    if x[0] == 1:
        a.append(x[1])

b = []
for x in p:
    if x[1] == n:
        b.append(x[0])
if set(a) & set(b):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
eage=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    eage[a-1].append(b-1)
    eage[b-1].append(a-1)
for e in eage:
    i_to_1=False
    i_to_n=False
    for ee in e:
        if ee==0:
            i_to_1=True
        if ee==n-1:
            i_to_n=True
        
        if i_to_1==True and i_to_n==True:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
def main():
    islands, regular_boat = map(int, input().split())
    departure_from_island1 = []
    arrive_to_islandN = []
    for _ in range(regular_boat):
        start, final = map(int, input().split())
        if start == 1 and final == islands:
            continue
        elif start == 1:
            departure_from_island1.append(final)
        elif final == islands:
            arrive_to_islandN.append(start)
    print("POSSIBLE" if len(set(departure_from_island1) & set(arrive_to_islandN)) > 0 else "IMPOSSIBLE")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N,M=map(int,input().split())
G=[[]for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
dist=[-1]*N
d=deque()
dist[0]=0
d.append(0)
while(len(d)!=0):
    v=d[0]
    d.popleft()
    for nv in G[v]:
        if(dist[nv]!=-1):
            continue
        dist[nv]=dist[v]+1
        d.append(nv)
if(dist[N-1]==2):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
a=[[int(i) for i in input().split()] for l in range(M)]
l=[]
for x in a:
    if x[0]==1:l.append(x[1])
m=[]
for x in a:
    if x[1]==N:m.append(x[0])
if set(l) & set(m):
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Solution (Python):
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque([1])
visited = [False] * (n+1)
d = [0] * (n+1)

while q:
    now = q.popleft()
    visited[now] = True
    for i in graph[now]:
        if visited[i]:
            pass
        else:
            q.append(i)
            d[i] = d[now] + 1
if d[n] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
lis1 = []
lis2 = []
ans = "IMPOSSIBLE"
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        lis1.append(b)
    else:
        lis2.append((a,b))
lis2 = set(lis2)        
for j in lis1:
    if (j,n) in lis2:
        ans = "POSSIBLE"
    else:
        pass

print(ans)

Solution (Python):
n, m = map(int, input().split())
L = []
for i in range(m):
    a,b = map(int, input().split())
    L.append((a,b))

st,go = [],[]
for i in range(m):
    if 1 in L[i]:
        st.append(L[i][1])
    if n in L[i]:
        go.append(L[i][0])

if set(st)&set(go):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict


def check():
    N,M = map(int, input().split())
    B = []
    hune = defaultdict(list)
    for _ in range(M):
        a,b = map(int, input().split())
        if a == 1:
            B.append(b)
        hune[a].append(b)
    
    for b in B:
        for goal in hune[b]:
            if goal == N:
                print('POSSIBLE')
                return
    print('IMPOSSIBLE ')
    
check()

Solution (Python):
m,n=map(int,input().split())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))

dep = []
arr = []
for i in range(n):
    if a[i][0]==1:
        dep.append(a[i][1])
    if a[i][1]==m:
        arr.append(a[i][0])
dep=set(dep)
arr=set(arr)
ans=dep & arr

if len(ans)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N, M = [int(i) for i in input().split()]
ab = []

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
e = []
for d in ab:
    if d[1] == N:
        c.append(d[0])
    elif d[0] == 1:
        e.append(d[1])

if len(set(c) & set(e)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

from_1 = set(b for a, b in AB if a == 1)
to_N = set(a for a, b in AB if b == N)
print('POSSIBLE' if from_1 & to_N else 'IMPOSSIBLE')

Solution (Python):
def solve():
    N,M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    ret = False
    for cod_1 in graph[1]:
        if N in graph[cod_1]:
            ret = True
            
    print('POSSIBLE' if ret else 'IMPOSSIBLE')
    
solve()

Solution (Python):
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
cands = set(b if a == 1 else a for a, b in AB if a == 1 or b == 1)
if any(a in cands and b == n or b in cands and a == n for a, b in AB):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n, m = map(int, input().split())
x = []
for i in range(m):
    x.append(list(map(int, input().split())))

p1 = set()
p2 = set()
for i in x:
    if i[0] == 1:
       p1.add(i[1])
    elif i[1] == n:
        p2.add(i[0])

if len(p1 & p2) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())

a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())

ship_1 = []
ship_2 = []
for i in range(M):
    if a[i] == 1:
        ship_1.append(b[i])
    if b[i] == N:
        ship_2.append(a[i])

both = set(ship_1) & set(ship_2)
if len(both) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())

from collections import defaultdict
d = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)
    
if len(set(d[1]) & set(d[n])) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
a_set = set()
b_set = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        a_set.add(b)
    if b == N:
        b_set.add(a)


product = a_set & b_set
if len(product) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
s = []
e = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == N:
    e.append(a)
if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
from1 = set()
fromn = set()
a =[]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fromn.add(b)
    if b == n:
        from1.add(a)
if len(from1 & fromn)>0 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
ab = {}

for _ in range(m):
    a, b = map(int, input().split())
    if a not in ab:
        ab[a] = [b]
    else:
        ab[a].append(b)
ans = 0
for i in ab[1]:
    if i in ab:
        if n in ab[i]:
            ans = 1
        else:
            continue
    else:
        continue

if ans == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
from collections import defaultdict
d = defaultdict(int)

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

for i in li:
  if i[1] == N:
    d[i[0]] += 1

for i in li:
  if i[0] == 1 and d[i[1]] != 0:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
s1 = set()
s2 = set()

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        s1.add(b)
    if b == N:
        s2.add(a)

if len(s1.intersection(s2)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())
G = [[] for i in range(N)]
for i in range(M):
	a,b = map(lambda x: int(x)-1, input().split())
	G[a].append(b)
	G[b].append(a)

flag = False

def dfs(p, x, d):
	if d>=2:
		if x==N-1:
			global flag
			flag = True
		return

	for i in G[x]:
		if i==p:
			continue
		else:
			dfs(x,i,d+1)

dfs(-1,0,0)
print('POSSIBLE' if flag else 'IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
a = set()
b = set()
for i in range(m):
    a_,b_ = map(int,input().split())
    if a_ == 1:
        a.add(b_)
    if b_ == n:
        b.add(a_)
print("POSSIBLE" if a&b else "IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(m)]

a = []
b = []
for i in l:
    if i[0] == 1:
        a.append(i[1])
    if i[1] == n:
        b.append(i[0])

print("POSSIBLE" if len(set(a)&set(b)) > 0 else "IMPOSSIBLE")

Solution (Python):
def takahasi(n , m , a):

    ans = "IMPOSSIBLE"
    list1n = []

    for i in range(m):
        if a[i][0] == 1 or a[i][1] == n:
            list1n.append(a[i][1] if a[i][0] == 1 else a[i][0])

    if len(list1n) != len(set(list1n)):
        ans = "POSSIBLE"

    return ans

def main():
    n , m = map(int , input().split())
    a = [list(map(int,input().split())) for i in range(m)]
    print(takahasi(n , m , a))

if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
g = [[] for i in range(n)] 
for i in range(m):
    x,y = map(int,input().split()) 
    x,y = x-1,y-1
    g[x].append(y)
    g[y].append(x)

for i in g[0]:
    if n-1 in g[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
start = []
goal = []
for i in range(m):
    a, b = map(int,input().split())
    if a == 1:
        start.append(b)
    if b == n:
        goal.append(a)
if set(start) & set(goal):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())

from1 = [False]*max(N,M)
toN = [False]*max(N,M)
for i in range(M):
  a,b = map(int,input().split())
  if a ==1 or b ==1:
    from1[a-1 if a!= 1 else b-1]=True
  if a == N or b == N:
    toN[a-1 if a!= N else b-1]=True
cnt =0 
for i in range(M):
  cnt+=from1[i]&toN[i]
print("POSSIBLE" if cnt else "IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
G = [list() for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

flag = False
for i in G[1]:
    if N in G[i]:
        flag = True
        break

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

se1 = set()
se2 = set()

for a,b in AB:
  if a>b:
    a,b = b,a
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2


answer = 'POSSIBLE' if se else 'IMPOSSIBLE'
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque


n, m = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(m):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

DISTANCE = {i:-1 for i in range(1, n + 1)}
DISTANCE[1] = 0
QUEUE = deque([1])
while QUEUE:
    now = QUEUE.popleft()
    for v in GRAPH[now]:
        if DISTANCE[v] != -1:
            continue
        DISTANCE[v] = DISTANCE[now] + 1
        QUEUE.append(v)

print("POSSIBLE" if DISTANCE[n] == 2 else "IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")

Solution (Python):
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")

Solution (Python):
n,m = map(int, input().split())
d = {}
for _ in range(m):
    a,b = map(int, input().split())
    if a not in d:
        d[a] = {}
    if b not in d:
        d[b] = {}
    d[a][b] = d[b][a] = 1

for v in d.values():
    if 1 in v and n in v:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
ans = 0
dic = {str(i):0 for i in range(1,N)}
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        dic[str(b)] += 1
        if dic[str(b)] == 2:
            ans = 1
    if b == N:
        dic[str(a)] += 1
        if dic[str(a)] == 2:
            ans = 1
if ans == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
n, m = map(int, input().split())

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == n:
    e.append(a)

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
A=[]
B=[]
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
    if b == N:
        B.append(a)
if len(set(A) & set(B))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
cand_1 = []
cand_n = []
for i in range(m):
  a,b = map(int,input().split())
  if a == 1:
    cand_1.append(b)
  elif b == n:
    cand_n.append(a)
flag = set(cand_1) & set(cand_n)

print('POSSIBLE' if flag else 'IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(M)]
sorted_lst = sorted(lst, key=lambda x: x[0])
ans = 'IMPOSSIBLE'
lst_1 = [0] * N
for i in sorted_lst:
  if (i[0] == 1):
    lst_1[i[1]-1] = 1
  elif (lst_1[i[0]-1] and i[1] == N):
    ans = 'POSSIBLE'
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = []
b = []
for i in range(m):
    a_, b_ = map(int, input().split())
    if a_ == 1 or a_ == n or b_ == 1 or b_ == n:
        a.append(a_)
        b.append(b_)

x_min=[]
x_max=[]
for i in range(len(a)):
    if a[i] == 1 or b[i] == 1:
        x_max.append(max(a[i], b[i]))
    if a[i] == n or b[i] == n:
        x_min.append(min(a[i], b[i]))
x = x_min + x_max
if len(x) == len(set(x)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):

N,M=map(int,input().split())
L=[]
B=[]
A=[]
flg=0
cnt=0
for i in range(M):
    a,b=list(map(int,input().split()))
    L.append([a,b])
    if a==1:
        B.append(b)
        cnt+=1
    elif b==N:
        A.append(a)
        

ans=[]
if len(set(A)&set(B))==0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):

N,M=map(int,input().split())
G=[[] for i in range(N+1)]

for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)

flg=False

near=[False for i in range(N+1)]

for i in range(len(G[1])):
    near[G[1][i]]=True

for i in range(len(G[N])):
    if near[G[N][i]]:
        flg=True

if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):

N, M = map(int, input().split())
l = {}
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if b != 0:
        if a not in l.keys():
            l[a] = [b]
        else:
            l[a].append(b)
for k1 in l[0]:
    if k1 not in l.keys():
        continue
    for k2 in l[k1]:
        if k2 == N - 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")