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):
from collections import defaultdict
N, M = map(int, input().split())
route = defaultdict(int)
for _ in range(M):
    a, b = map(int, input().split())
    route[a, b] = 1
for i in range(2, N):
    if route[1, i] == route[i, N] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):


def main():
    n, m = map(int, input().split())

    arry = []
    cnt = 0
    for i in range(m):
        a, b = map(int, input().split())
        if a == 1:
            cnt += 1
            arry.append(b)
        elif b == n:
            cnt += 1
            arry.append(a)
    if len(set(arry)) < cnt:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

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

from_one, to_n = set(), set()
for ab_i in ab:
	if ab_i[0] == 1:
		from_one.add(ab_i[1])
	elif ab_i[1] == n:
		to_n.add(ab_i[0])
	
print("POSSIBLE" if from_one & to_n else "IMPOSSIBLE")

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

s=d[1]
f=True
for i in s:
  if N in d[i]:
    print("POSSIBLE")
    f=False
    break
if f:print("IMPOSSIBLE")

Solution (Python):
def inpl(): return input().split()
def get_str(bl): return 'POSSIBLE' if bl else 'IMPOSSIBLE'

n, m = map(int, inpl())
M = list(tuple(map(int, inpl())) for _ in range(m))
X = list(tuple((a, b)) for a, b in M if a == 1)
Y = list(tuple((a, b)) for a, b in M if b == n)
XB = set(list(b for _, b in X))
YA = set(list(a for a, _ in Y))
print(get_str(len(XB & YA) > 0))

Solution (Python):
N, M = map(int,input().split())
t_mid = set()
f_mid = set()
for _ in range(M):
    f, t = map(int,input().split())
    if f == 1:
        t_mid.add(t)
    elif t == N:
        f_mid.add(f)

if t_mid & f_mid:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
b = set()
for i in a:
    if i[0]==1 or i[1]==N:
        b.add((i[0],i[1]))
for i in range(2,N):
    if (1,i) in b and (i,N) in b:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')

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

first = []
second = []
flag = 0
end = True

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append(a)
  if a == 1:
    first.append(b)

first.sort()
second.sort()
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  firsti = 0
  secondi = 0
  while(end == True):
    if first[firsti] == second[secondi]:
      print("POSSIBLE")
      break
    elif first[firsti] < second[secondi]:
      firsti += 1
      if firsti > len(first) - 1:
        print("IMPOSSIBLE")
        break
    else:
      secondi += 1
      if secondi > len(second) - 1:
        print("IMPOSSIBLE")
        break

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

import heapq
from collections import defaultdict
nodes = defaultdict(list)


for e in edges:
    nodes[e[0] - 1].append((1, e[1] - 1))
    nodes[e[1] - 1].append((1, e[0] - 1))


INF = float('inf')

def dijkstra(x):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist

dist = dijkstra(0)

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

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())

shima = []
ans = "IMPOSSIBLE"

for i in range(M):
  a,b = map(int ,input().split())
  if a == 1: shima.append(b-1)
  if b == N: shima.append(a-1)
    
shima.sort()
for s,t in zip(shima[:-1],shima[1:]):
  if s == t:
    ans = "POSSIBLE"
    break
 
print(ans)

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

hop_before = []
hop_to = []

hop_dict = {}

for i in range(M) :
    a, b = map(int, input().split())
    
    if a == 1 :
        if b in hop_dict.keys() :
            hop_dict[b] += 1
        else :
            hop_dict[b] = 1
    if b == N :
        if a in hop_dict.keys() :
            hop_dict[a] += 1
        else :
            hop_dict[a] = 1
        
possible = False
for i in hop_dict.keys() :
    if hop_dict[i] >= 2 :
        print("POSSIBLE")
        possible = True
        break
        
if possible == False :
    print("IMPOSSIBLE")

Solution (Python):


N, M = map(int, input().split())


transit = [False] * N

transit2 = [False] * N

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        transit[b] = True
    if b == N:
        transit2[a] = True

for i in range(N):
    if transit[i] and transit2[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):


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

transit = []
transit2 = []
for i in range(M):
    if abM[i][0] == 1:
        transit.append(abM[i][1])
    if abM[i][1] == N:
        transit2.append(abM[i][0])


if len(set(transit) & set(transit2)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

iki=[]
kae=[]

c=0
flag=-1

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

l=len(iki)
iki2=set(iki)
l2=len(iki2)


                
if l>l2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
a,b={-1},{0}
for i in range(m):
    x,y=map(int,input().split())
    if x==1: a.add(y)
    if y==n: b.add(x)
print("POSSIBLE" if (len(a&b)) else "IMPOSSIBLE")

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

Solution (Python):
N,M=map(int,input().split())
a = [0 for i in range(N)]
b = [0 for i in range(N)]
for i in range(M):
    link=list(map(int,input().split()))
    link.sort()
    if link[0] == 1:
        a[link[1]-1] = 1
    if link[1] == N:
        b[link[0]-1] = 1
for i in range(N):
    if a[i]*b[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):


n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(m)]

set1 = set()
setN = set()
for a in A:
    if a[0] == 1:
        set1.add(a[1])
    elif a[1] == n:
        setN.add(a[0])

if len(set1.intersection(setN)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
import bisect
N,M=map(int,input().split())
grid = []
for i in range(M):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
pre = []
pos = []
for ships in grid:
  if ships[0] == 1:
    pre.append(ships[1])
  if ships[1] == N:
    pos.append(ships[0])
if pre == [] or pos == []:
  print('IMPOSSIBLE')
  sys.exit()
pre.sort()
pos.sort()
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return 1
    return 0
for nums in pre:
  if index(pos,nums) == 1:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Solution (Python):
N,M =[int(i) for i in input().split(' ')]
table = [0]*N

for i in range(M):
    a,b = [int(i) for i in input().split(' ')]
    if a==1:
        table[b-1] +=1
        if b==N:
            table[b-1] +=1
    if b==N:
        table[a-1]+=1

flag = True
for i in table:
    if i==2:
        print("POSSIBLE")
        flag = False
        break

if flag:
    print("IMPOSSIBLE")

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)



INF = float("inf")


def BFS(G, s):
    n = len(G)
    q = deque()
    D = [INF] * n
    q.append(s)
    D[s] = 0
    while len(q) != 0:
        p = q.popleft()
        for i in G[p]:
            if D[i] == INF:
                q.append(i)
                D[i] = D[p] + 1
    if D[n - 1] == 2:
        return "POSSIBLE"
    else:
        return "IMPOSSIBLE"


print(BFS(G, 0))

Solution (Python):
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
ahoge.sort()
hanege.sort()
def bis(i):
    under = 0
    upper = len(hanege)-1
    while under <= upper:
        l = (under+upper)//2
        if i == hanege[l]:
            return 1
        elif i < hanege[l]:
            upper = l-1
        elif i > hanege[l]:
            under = l+1
    return 0
flag = 0
for i in ahoge:
    if bis(i) == 1:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Solution (Python):
import math


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

d_1 = []
d_N = []

for e in edge_lst:
    if e[0] == 1:
        d_1.append(e[1])
    if e[1] == N:
        d_N.append(e[0])

ans = list(set(d_1) & set(d_N))

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

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

xs = {}

for a, b in ab:
    if a == 1:
        xs[b] = 1

result = 0

for a, b in ab:
    if b == N and a in xs:
        result = 1
        break

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

Solution (Python):
from operator import itemgetter
from collections import Counter
N,M = map(int,input().split())
ab = {tuple(map(int,input().split())) for _ in range(M)}
if M == 1:
    print('IMPOSSIBLE')
    exit()
ab = [i[1] if i[0] == 1 else i[0] for i in ab if i[0] == 1 or i[1] == N]
c = Counter(ab)
if c.most_common(1)[0][1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
to = set()
fr = set()
for a,b in src:
    if a == 1: to.add(b)
    if b == N: fr.add(a)
print('POSSIBLE' if to&fr else 'IMPOSSIBLE')

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

first_element = set()
second_element = set()

for element in input_list:
    if element[0] == 1:
        first_element.add(element[1])
    elif element[1] == N:
        second_element.add(element[0])

if first_element & second_element:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int, input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
x,y=[],[]
for s in ab:
    if s[0]==1:
        x.append(s[1])
    if s[1]==n:
        y.append(s[0])

print("POSSIBLE" if len(set(x)&set(y))>0 else "IMPOSSIBLE")

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

for i in arr:
    if i[0] == 1:
        one.add(i[1])
    elif i[1] == n:
        two.add(i[0])

if len(one & two) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

q = []
for i in range(len(branch[1])):
	q.append(branch[1][i])

check = False
for i in range(len(q)):
	if n in branch[q[i]]:
		check = True
		break
if check:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Solution (Python):
N, M = map(int,input().split())
reachable = False
from_start = []
to_end = []

for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        from_start.append(b)
    elif b == N:
        to_end.append(a)

if len(set(from_start).intersection(set(to_end))) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

if len(s & e) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):





if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    set_a = set()
    set_b = set()

    for i in range(m):
        a, b = list(map(int, input().split()))

        if a == 1:
            set_b.add(b)
        elif b == n:
            set_a.add(a)

    if set_a & set_b:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Solution (Python):





if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    set_a = set()
    set_b = set()

    for i in range(m):
        a, b = list(map(int, input().split()))

        if a == 1:
            set_b.add(b)
        elif b == n:
            set_a.add(a)

    if len(set_a & set_b) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Solution (Python):
import sys

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

mid1 = set()
mid2 = set()
for _ in range(m):
    a,b, = map(int, input().split())
    if a == 1:
        mid1.add(b)
    elif b == n:
        mid2.add(a)
result = bool(mid1 & mid2)
if result:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
ab, c, d = [], set(), set()
for i in range(m):
    ab.append(list(map(int, input().split())))
for i in range(m):
    if(ab[i][0] == n):
        c.add(ab[i][1])
    elif(ab[i][1] == n):
        c.add(ab[i][0])
    elif(ab[i][0] == 1):
        d.add(ab[i][1])
    elif(ab[i][1] == 1):
        d.add(ab[i][0])
if(c & d):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def main():
    n, m = map(int, input().split())
    a, b = [], []
    from_1 = set()
    to_n = set()
    for _ in range(m):
        x, y = map(int, input().split())
        if x == 1:
            from_1.add(y)
            continue
        if y == n:
            to_n.add(x)
            continue
    ans = from_1 & to_n
    if ans:
        return "POSSIBLE"

    return 'IMPOSSIBLE'


print(main())

Solution (Python):
n, m = map(int,input().split())
from1 = [False]*(n+1)
toN = [False]*(n+1)
for _ in range(m):
    a, b = map(int,input().split())
    if a > b:
        a, b = b, a
    if a == 1:
        from1[b] = True
    if b == n:
        toN[a] = True
for i in range(n):
    if from1[i] and toN[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split(' '))
ferrys = [list(map(int, input().split(' '))) for _ in range(M)]
cand1to = []
candtoN = []
for f in ferrys:
    if f[0] == 1:
        cand1to.append(f[1])
    elif f[1] == 1:
        cand1to.append(f[0])
    elif f[0] == N:
        candtoN.append(f[1])
    elif f[1] == N:
        candtoN.append(f[0])

if set(cand1to) & set(candtoN) == set([]):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

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

for i in range(m):
  a, b = map(int, input().split())
  l[a].append(b)
def f():
  for i in l[1]:
    if n in l[i]:
      return 'POSSIBLE'
  
  return 'IMPOSSIBLE'
print(f())

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

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

for i in range(m):
    island_set.add(tuple(map(int, input().split())))

for i in range(2, n):
    if (1, i) in island_set:
        if (i, n) in island_set:
            print("POSSIBLE")
            break

else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=[int(i) for i in input().split()]
p=[[0 for i in range(2)] for j in range(m)]

a=[0 for i in range(n+1)]
b=[0 for i in range(n+1)]

for i in range(m):
  p[i]=[int(i) for i in input().split()]

for i in range(m):  
  
  if p[i][0]==1:
    a[p[i][1]]+=1
    
  elif p[i][1]==n:
    a[p[i][0]]+=1
   
    
if max(a)>=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def inpl(): return list(map(int, input().split()))
N, M = inpl()
a1, aN, b1, bN = set(), set(), set(), set()
for i in range(M):
    temp_a, temp_b = inpl()
    if temp_a == 1:
        a1.add(temp_b)
    elif temp_a == N:
        aN.add(temp_b)
    
    if temp_b == 1:
        b1.add(temp_a)
    elif temp_b == N:
        bN.add(temp_a)

if len(a1&bN)!=0 or len(aN&b1)!=0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

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

print('POSSIBLE' if len(s1&s2) else 'IMPOSSIBLE')

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

boolins =[]
for i in range(n):
    boolins.append(0)
    
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        boolins[xxx[1]] = boolins[xxx[1]] + 1
    elif xxx[1] == n :
        boolins[xxx[0]]=boolins[xxx[0]]+ 1
    else:
        None


if 2 in boolins:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

Solution (Python):
n, m = (int(i) for i in input().split())
a,b = [0 for i in range(m)],[0 for i in range(m)]
g = [[] for i in range(n)]
OK = False 
for i in range(m):
    a[i],b[i] = map(int, input().split())
    a[i]-=1
    b[i]-=1
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
for i in range(m):
    if a[i]==0 and n-1 in g[b[i]]:
        OK = True
print('POSSIBLE' if OK else 'IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
s=[]
for j in range(M):
    x=list(map(int,input().split()))
    if N in x and 1 in x:
        print("POSSIBLE")
        exit()
    if N in x:
        x.remove(N)
        s+=x
    if 1 in x:
        x.remove(1)
        s+=x
if len(list(set(s)))!=len(s):
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

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

rou = [[] for i in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	rou[a-1].append(b-1)
	rou[b-1].append(a-1)
for i in rou[0]:
	for j in rou[i]:
		if j == n-1:
			print("POSSIBLE")
			exit()
print("IMPOSSIBLE")

Solution (Python):
def read_boats(n, m):
    boats = [[] for i in range(max(n, m) + 1)]
    for i in range(m):
        a, b = map(int, input().split())
        boats[a].append(b)
    return boats

def trip(n, boats):
    for origin in boats[1]:
        if n in boats[origin]:
            return('POSSIBLE')
    return('IMPOSSIBLE')


if __name__ == '__main__':
    n, m = map(int, input().split())
    boats = read_boats(n, m)
    print(trip(n, boats))

Solution (Python):
def c_cat_snuke_and_a_voyage(N, M, I):
    p = [False] * N  
    q = [False] * N  
    for a, b in I:
        if a == 1:  
            p[b] = True
        elif b == N:  
            q[a] = True
    ans = 'IMPOSSIBLE'
    for i in range(N):
        if p[i] and q[i]:
            ans = 'POSSIBLE'
            break  
    return ans

N,M = [int(i) for i in input().split()]
I = [[int(i) for i in input().split()] for j in range(M)]
print(c_cat_snuke_and_a_voyage(N, M, I))

Solution (Python):
n, m = map(int, input().split())
s = set()
e = set()
p = False
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        if b in e:
            p = True
            break
        s.add(b)
    if b == n:
        if a in s:
            p = True
            break
        e.add(a)

if p: print('POSSIBLE')
else: print('IMPOSSIBLE')

Solution (Python):


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

a, b = [], []
ok = [False for x in range(n + 1)]

for i in range(m):
    x, y = map(int, input().split())
    a += [x]
    b += [y]
    if x == 1:
        ok[y] = True

for i in range(m):
    x, y = a[i], b[i]
    if ok[x] and y == n:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

for i in range(m):
  temp = list(map(int, input().split()))
  ship[temp[0]-1].append(temp)

for i in range(len(ship[0])):
  now = ship[0][i]
  if [now[1], n] in ship[now[1]-1]:
    flag = True
    break

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

Solution (Python):
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
a ,b= [],[]
for i in x:
	if i[0]==1:
		a.append(i[1])
	if i[1]==n:
		b.append(i[0])
if len(a)+len(b) == len(set(a+b)): print("IMPOSSIBLE")
else: print("POSSIBLE")

Solution (Python):
N,M = map(int,input().split())
from1 = set()
ton = set()
for i in range(M):
  l,r = map(int,input().split())
  if l == 1:
    from1.add(r)
  if r == N:
    ton.add(l)
if len(from1&ton) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
[n,m] = list(map(int,input().split(' ')))
L1 = [0]*n
Ln = [0]*n
i=0
while i < m:
    l0 = list(map(int,input().split(' ')))
    if l0[0] == 1:
        L1[l0[1]] = 1
    elif l0[1] == n:
        Ln[l0[0]] = 1
    i += 1
q = 0
while q < n:
    if L1[q] * Ln[q] == 1:
        print('POSSIBLE')
        q = 0
        break
    else:
        q += 1
if q != 0:
    print('IMPOSSIBLE')

Solution (Python):
import sys
n,m=map(int,input().split())
INF=10**15
li1=set()
lin=set()
for i in range(m):
  a,b=map(int,input().split())
  if(a==1):li1.add(b)
  elif(b==1):li1.add(a)
  elif(a==n):lin.add(b)
  elif(b==n):lin.add(a)
for i in li1:
  if(i in lin):
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

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

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

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

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

s = []
g = []

for ship in ships:
    if ship[0] == 1:
        s.append(ship[1])
    if ship[1] == N:
        g.append(ship[0])

res = False

if not (len(s) == 0 or len(g) == 0):
    res = not set(s).isdisjoint(set(g))

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

Solution (Python):
n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
goal = []

for ship in ships:
    if n in ship:
        goal.append(ship[0])
    elif 1 in ship:
        relay.append(ship[1])

res = False
if len(goal) == 0 or len(relay) == 0:
    print("IMPOSSIBLE")

else:
    print("IMPOSSIBLE" if not set(relay) & set(goal) else "POSSIBLE")

Solution (Python):
n,m = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(m)]
B = []
C = []
for i in A:
    if 1 in i:
        B += i
B = set(B)
for i in A:
    a,b = i
    if a in B:
        C.append(b)
    elif b in B:
        C.append(a)
        
C = set(C)

if n in C or n in B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
g,l=input().split()
c=int(l)
a=[]
n=[]
m=[]

for i in range(c):
  i1,i2=input().split()
  a.append([i1,i2])
  if i1 =='1':
    n.append(i2)
  if i2 =='1':
    n.append(i1)
  if i1 ==g:
    m.append(i2)
  if i2 ==g:
    m.append(i1)

if list(set(m) & set(n)):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
route = [[] for i in range(n + 1)]
for j in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
for h in set(route[1]):
    for b in set(route[h]):
        if b == n:
            print("POSSIBLE")
            exit()
else:
    print("IMPOSSIBLE")

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

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

toN = list(filter(lambda x: N in x, AB))
toN = set([flatten for inner in toN for flatten in inner])
frm_first = list(filter(lambda x: 1 in x, AB))
frm_first = set([flatten for inner in frm_first for flatten in inner])

if toN & frm_first:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
c = []
d = []
flag = 0
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == 1:
        c.append(b[i])
        if b[i] == N:
            flag = 1
    if b[i] == N:
        d.append(a[i])
        if a[i] == 1:
            flag = 1
e = set(c) | set(d)
if len(c) + len(d) == len(e):
    flag = 0
else:
    flag = 1

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

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

E = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    e = E.get(a, None)
    if e is None:
        e = []
    e.append(b)
    E[a] = e
    e = E.get(b, None)
    if e is None:
        e = []
    e.append(a)
    E[b] = e


def foo(E):
    for i in range(1, n):
        if i in E and 1 in E[i] and n in E[i]:
            return True
    return False

if foo(E):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

for i in range(len(A[0])):
    if len(A[A[0][i]]) is not 0:
        if N-1 in A[A[0][i]]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
q = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        p = P[i][1]
        if q < 0:
            if i > 0:
                q = i - 1
            else:
                q = 0
        for j in range(q, M):
            if P[j][0] == p:
                if P[j][1] == N:
                    ans = ("POSSIBLE")
                    break
            elif P[j][0] > p:
                if q >= 0:
                    q = j - 1
                else:
                    q = 0
                break
    else:
        break
print(ans)

Solution (Python):
N,M = map(int,input().split(" "))
a_to = []
N_to = []
for i in range(M):
	a, b = map(int,input().split(" "))
	if a == 1 or b == 1:
		a_to.append(max(a,b))
	elif b == N or a == N:
		N_to.append(min(a,b))

a_set = set(a_to)
N_set = set(N_to)

if (len(a_set&N_set) >= 1):
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Solution (Python):

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

ok1 = [False] * n
ok2 = [False] * n

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a == 0:
        ok1[b] = True
    if b == n - 1:
        ok2[a] = True

for m in range(n):
    if ok1[m] and ok2[m]:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
aa = [[]*n for i in range(n)]
ans = "IMPOSSIBLE"
for i in range(m):
  k = list(map(int, input().split()))
  aa[k[0]-1].append(k[1]-1)
  aa[k[1]-1].append(k[0]-1)
tmp = aa[0]
for j in range(len(tmp)):
  if n-1 in aa[tmp[j]]:
    ans = "POSSIBLE"
print(ans)

Solution (Python):
N, M =map(int,input().split())
F=[]
L=[]


for i in range(M):
    a, b=map(int,input().split())
    if a==1:
        F.append(b)

    if b==N:
        L.append(a)

FF=set(F)
LL=set(L)

for _ in FF:
    if _ in LL:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

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

island = [[]for i in range(n+1)]

for i in range(m):
    a,b = map(int, input().split(' '))
    island[a].append(b)
    island[b].append(a)

flag = True

for i in island[1]:
    for k in island[i]:
        if k == n:
            print('POSSIBLE')
            flag = False
            break
    if flag is False:
        break

if flag is True:
    print('IMPOSSIBLE')

Solution (Python):

N,M = list(map(int,input().split()))

edge_1toANY = [0 for n in range(N+1)]
edge_ANYtoN = [0 for n in range(N+1)]

for m in range(M):
    a,b = list(map(int,input().split()))
    if a == 1:
        edge_1toANY[b] = 1
    if b == N:
        edge_ANYtoN[a] = 1

flag = False
for n in range(N+1):
    if edge_1toANY[n] == 1:
        if edge_ANYtoN[n] == 1:
            flag = True
            break

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