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.



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

contact = [[] for _ in range(N)]

for a, b in ab:
	contact[a-1].append(b-1)
	contact[b-1].append(a-1)

#print(contact)

for x in contact[0]:
	if N-1 in contact[x]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

#print(graph)
#print(graph[0])

for x in graph[0]:
	for y in graph[x]:
		if y == N-1:
			print("POSSIBLE")
			break
	else:
		continue
	break
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
#重み付き隣接リスト(weight-first)
n,m = map(int,readline().split())
g = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    w = 1
    g[x].append((w,y))
    g[y].append((w,x))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)

dist = dijkstra_heap(0,g)[-1]
print("POSSIBLE" if dist == 2 else "IMPOSSIBLE")

Submission status: Accepted

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

if m == 1:
  print("IMPOSSIBLE")

else:
  root = [[] for i in range(n)]
  for a, b in ab:
    root[a-1].append(b-1)
  
  flag = False
  for j in root[0]:
    if n-1 in root[j]:
      flag = True
      break

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
p="POSSIBLE"
S=set()
a=[]
for _ in range(M):
    A, B = map(int, input().split())
    if A == 1:
        a.append(B)
    else:
        S.add((A,B))
print(p if any([(i,N) in S for i in a]) else "IM"+p)

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(m))


def dfs(now, count):
    if count <= 2 and visit[n] == 0:
        visit[now] = 1
        if count <= 1:
            for x in graph[now]:
                dfs(x, count + 1)


flag = False
if ab[0][0] == 1:
    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    dfs(1, 0)

    if visit[n] == 1:
        flag = True

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab_list = [list(map(int,input().split())) 
           for nesya in range(m)]
start = set()
end = set()
for ab in ab_list:
  if ab[0] == 1:
    start.add(ab[1])
  elif ab[1] == n:
    end.add(ab[0])
ans = start&end
if len(ans) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab_list = [list(map(int,input().split())) 
           for nesya in range(m)]
start = set()
end = set()
for ab in ab_list:
  if ab[0] == 1:
    start.add(ab[1])
  if ab[1] == n:
    end.add(ab[0])
ans = start&end
if len(ans) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
memo = [[] for _ in range(N+1)]

for _ in range(M):
    ai, bi = map(int, input().split())
    memo[ai].append(bi)
    memo[bi].append(ai)

queue = memo[1]

#島1から直通の場合
if N in queue:
    print("POSSIBLE")
    quit()

#島1から定期便2つ以内に島Nにたどり着けるかどうか確認する
while queue:
    island = queue.pop()
    for connected_island in memo[island]:
        if connected_island == N:
            print("POSSIBLE")
            quit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  temp=set(temp)
  tempb=set(tempb)
  c = temp&tempb
  #c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
n,m = list(map(int, input().split()))

d=defaultdict(list)
for _ in range(m):
    a,b = list(map(int, input().split()))
    d[b].append(a)

for src in d[n]:
    if 1 in d[src]:
        print('POSSIBLE')
        exit()
        
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
one2other = [0]*N
other2goal = [0]*N
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        one2other[b-1] = 1
    if b == N:
        other2goal[a-1] = 1
for i in range(N):
    if one2other[i] == 1 and other2goal[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

ans = "IMPOSSIBLE"

start_candidate = [X[1] for X in s if X[0]==1 ]
goal_candidate = [X[0] for X in s if X[1]==N]

ans = len(start_candidate)+len(goal_candidate)-len(set(start_candidate+goal_candidate))
if ans != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

G = [[] for _ in range(N)]
for x, y in L:
  x, y = x-1, y-1
  G[x].append(y)
  G[y].append(x)

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

Submission status: Accepted

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

G = [[] for _ in range(N)]
for x, y in L:
  x, y = x-1, y-1
  G[x].append(y)
  G[y].append(x)

for v in G[0]:
  for nv in G[v]:
    if nv == N-1:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
n,m = iim()
cand = []
check = []
for i in range(m):
    a,b = iim()
    if a == 1:
        cand.append(b)
    if b == n:
        check.append(a)

cand = set(cand)
flag=False
for i in check:
    if i in cand:
        flag = True

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
one = []
goal = []
for i in range(M):
    A,B = map(int,input().split())

    if A == 1 :
        one.append(B)
    elif B == 1:
        one.append(A)

    if A == N or B == N:
        goal.append(A)
        goal.append(B)

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

Submission status: Accepted

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

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# sys.stdin.readline()
import numpy as np
import math
import sys
input = sys.stdin.readline
n,m= map(int,input().split())
A = []
B = []
for i in range(m):
    x,y = map(int,input().split())
    if x==1:
        A.append(y)
    elif y==1:
        A.append(x)
    elif x==n:
        B.append(y)
    elif y==n:
        B.append(x)
s  ="IMPOSSIBLE" if len(set(A + B)) ==len(A)+len(B) else "POSSIBLE"
print(s)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d = {str(x):[] for x in range(1,n+1)}
n = str(n)
ans = "IMPOSSIBLE"
for i in range(m):
    t = input().split()
    d[t[0]].append(t[1])

for l1 in d["1"]:
    if l1==n:
        ans="POSSIBLE"
        break
    else:
        for l2 in d[l1]:
            if l2==n:
                ans="POSSIBLE"
                break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d = {str(x):[] for x in range(1,n+1)}
n = str(n)
ans = "IMPOSSIBLE"
for i in range(m):
    t = input().split()
    d[t[0]].append(t)

for l1 in d["1"]:
    if l1[1]==n:
        ans="POSSIBLE"
    else:
        for l2 in d[l1[1]]:
            if l2[1]==n:
                ans="POSSIBLE"
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = []

n1 = set()
nN = set()

for _ in range(M):
    a, b = map(int, input().split())
    if (a == 1) or (b == 1):
        n1.add(b if a == 1 else a)
    if (a == N) or (b == N):
        nN.add(b if a == N else a)

ans = 'IMPOSSIBLE'
if len(n1 & nN) > 0:
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
li = []
for ab in AB:
    if ab[0] == 1:
        li.append(ab[1])
    if ab[1] == N:
        li.append(ab[0])
se = set(li)
if len(se) != len(li):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

s = []
g = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)
    
ans = set(s) & set(g)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

paths = defaultdict(set)

for start, end in edges:
    if start == 1:
        paths[end] |= {start, end}
    elif end == N:
        paths[start] |= {start, end}

for path in paths.values():
    if {1, N}.issubset(path):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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


def input():
    return sys.stdin.readline()[:-1]


N, M = map(int, input().split())
from_1 = {}
to_n = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b] = True
    elif b == N:
        to_n[a] = True

for key in to_n.keys():
    if key in from_1:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(s):
    from collections import deque
    check = [0] * (n + 1)
    stack = deque([s])
    check[s] = 0
    while stack:
        now = stack.pop()
        for next in graph[now]:
            if check[next] != 0 and next != n:
                continue
            if next == n and check[now] == 1:
                print('POSSIBLE')
                exit()
            check[next] += check[now] + 1
            stack.appendleft(next)


dfs(1)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [tuple(readnums()) for _ in range(M)]
    
    al = {x[1] for x in ab if x[0] == 1}
    bl = {x[0] for x in ab if x[1] == N}
    print('POSSIBLE' if al & bl else 'IMPOSSIBLE')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

ans = set(starts) & set(goals)

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

Submission status: Accepted

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

A = [0] * n
B = [0] * n

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

for i in range(n):
    if A[i] == B[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue May 12 14:41:02 2020

@author: shinba
"""

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

data = []
relay = []

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

ans = set(relay) & set(data)

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

Submission status: Accepted

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

k=[]
l=[]
ans=0
for i in range(m):
    input_l = sorted(list(map(int,input().split())))
    if input_l[0]==1:
        k.append(input_l[1])
    if input_l[1]==n:
        l.append(input_l[0])
print('IMPOSSIBLE' if len(set(k)&set(l))==0 else 'POSSIBLE')

Submission status: Accepted

Solution code:
island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        temp.append(route[j][0])
 
 
print("POSSIBLE") if len(temp) != len(list(set(temp))) else print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
li = []
for n in range(M):
    A,B = map(int, input().split())
    li.append([A,B])
p = []
q = []
for i in li:
    if i[0]==1:
        p.append(i[1])
for i in li:
    if i[1]==N:
        q.append(i[0])
if set(p) &set(q):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE ')

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split());n,m=I();p="POSSIBLE";c={tuple(I())for _ in[0]*m}
for i in range(2,n):
 if{(1,i),(i,n)}<=c:print(p);exit()
print("IM"+p)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = {tuple(map(int, input().split())) for _ in [None]*m}
for i in range(2, n):
    if {(1, i), (i, n)} <= c:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        temp.append(route[j][0])


print("POSSIBLE") if len(temp) != len(list(set(temp))) else print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

def resolve():
    N,M=pin()
    a=set()
    b=set()
    for i in range(M):
        s,t=pin()
        if s==1:a.add(t)
        if t==N:b.add(s)
    x=len(a&b)
    print(["IMPOSSIBLE","POSSIBLE"][x>0])    
        

    
        
#%%submit!    
resolve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d={i:[] for i in range(n)}
n-=1
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
for i in d[0]:
    if n in d[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
x=[]
y=[]
for i in range(m):
    a,b=mp()
    if a==1:
        x.append(b)
    if b==n:
        y.append(a)
if len(list(set(x) & set(y)))>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def check():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a,b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    for v in edge[0]:
        if N-1 in edge[v]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'
print(check())

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, m = ns()
    d = [[] for i in range(n)]

    for _ in range(m):
        a, b = ns()
        a -= 1
        b -= 1
        d[a].append(b)
        d[b].append(a)

    start = set(d[0])
    term = set(d[n-1])

    for si in start:
        if si in term:
            print("POSSIBLE")
            exit(0)

    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [list(readnums()) for _ in range(M)]

    s1 = {x[1] for x in ab if x[0] == 1}
    s2 = {x[0] for x in ab if x[1] == N}

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

def main():
  n,m=nii()

  tree=[[] for i in range(n)]
  for i in range(m):
    a,b=nii()
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

  for i in tree[0]:
    for j in tree[i]:
      if j==n-1:
        print('POSSIBLE')
        exit()
  print('IMPOSSIBLE')

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

def main():
  n,m=nii()

  tree=[[] for i in range(n)]
  for i in range(m):
    a,b=nii()
    a-=1
    b-=1
    tree[a]+=[b]
    tree[b]+=[a]

  for i in tree[0]:
    for j in tree[i]:
      if j==n-1:
        print('POSSIBLE')
        exit()
  print('IMPOSSIBLE')

if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m=nii()

tree=[[] for i in range(n)]
for i in range(m):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

for i in tree[0]:
  for j in tree[i]:
    if j==n-1:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

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

for i in tree[0]:
  for j in tree[i]:
    if j==n-1:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def check():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a,b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    for v in edge[0]:
        if N-1 in edge[v]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'
print(check())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc068/submissions/12987221
# C - Cat Snuke and a Voyage
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    for i in edge[0]:
        if n - 1 in set(edge[i]):
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

if len(ab) != len(set(ab)):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    intersect = {u_1 for u_1 in g[0]} & {u_N for u_N in g[N - 1]}
    print('POSSIBLE' if intersect else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans="IMPOSSIBLE"
li=[0]*N

for ab in AB:
    if 1 in ab:
        for i in ab:
            if i!=1:
                if li[i-1]==-1:
                    ans="POSSIBLE"
                    break
                else:
                    li[i-1]=1
    elif N in ab:
        for i in ab:
            if i!=N:
                if li[i-1]==1:
                    ans="POSSIBLE"
                    break
                else:
                    li[i-1]=-1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().split())
        a -= 1; b -= 1
        graph[a].append(b)
    check = [0] * N

    que = deque()
    cnt = 0

    que.extend(graph[0])
    flag = False
    ans = 'IMPOSSIBLE'
    while len(que) > 0:
        q = que.pop()
        for i in graph[q]:
            if i == N-1:
                ans = 'POSSIBLE'
                flag = True
                break
        if flag:
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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)

if (X & Y) == set():
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
b = []

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

if set(a) & set(b):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

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

for i in range(M):
    a,b = map(int,input().split())
    a,b = min(a,b), max(a,b)
    if a == 1:
        x[b] = True
    if b == N:
        y[a] = True

ans = 'IMPOSSIBLE'
for i in range(N+1):
    if x[i] and y[i]:
        ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [set() for _ in range(N)]

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

if len(G[N - 1] & G[0]) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [set() for _ in range(N)]

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

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

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans=dict()
for i in range(m):
  a,b=map(int,input().split())
  if not(a in ans):
    ans[a]={b,}
  else:
    ans[a].add(b)
  if not(b in ans):
    ans[b]={a,}
  else:
    ans[b].add(a)    
flag=False

for i in ans[1]:
  if n in ans[i]:
    flag=True
    break
    

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m=MI()
lis=[LI() for i in range(m)]
nums=[]
for i in range(m):
    if lis[i][0]==1:
        nums.append(lis[i][1])
    if lis[i][1]==n:
        nums.append(lis[i][0])
#print(nums)
if len(nums)>len(list(set(nums))):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    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)
    if len(sa&sb) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

flag = False
def dfs(now, prev, cnt):
    global flag
    if cnt == 2:
      if now == n-1:
        flag = True
    for next in g[now]:
        if next != prev and cnt < 2:
            dfs(next, now, cnt+1)
    return flag
            
ans = dfs(0,-1,0)
if ans:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(m):
  c,d=map(int,input().split())
  if c==1:
    a[d-1]=1
  if d==n:
    b[c-1]=1
success=0
for i in range(1,n):
  if a[i]*b[i]==1:
    success=1
if success==1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
l = [0] * (n+1)
for _ in range(m):
  a,b = map(int, input().split())
  if a == 1: l[b] += 1
  if b == n: l[a] += 1

print("POSSIBLE" if 2 in l else "IMPOSSIBLE")