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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    print("ABC"+str(n))
    return

#B
def B():
    ni = [2 ** i for i in range(1, 10)]
    n = II()
    ans = 1
    for i in range(1, n + 1):
        if i in ni:
            ans = i
    print(ans)        
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    next = []
    for i in edg[0]:
        next.append(i)
    for ne in next:
        for i in edg[ne]:
            if i == n - 1:
                print("POSSIBLE")
                return
    print("IMPOSSIBLE")
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
T = [[]for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
ans = "IMPOSSIBLE"
def f(v,p,n):
    global N,T,ans
    if n>2: return
    if n==2 and v==N: ans="POSSIBLE"
    for c in T[v]:
        if c!=p: f(c,v,n+1)
f(1,0,0)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC68 C

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

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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


goal_ship = set()
transit = set()

for i in ship:
    if i[1] == N:
        goal_ship.add(i[0])
for i in ship:
    if i[0] == 1:
        transit.add(i[1])

ans = goal_ship & transit

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

Submission status: Accepted

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


goal_ship = []
transit = []

for i in ship:
    if i[1] == N:
        goal_ship.append(i[0])
for i in ship:
    if i[0] == 1:
        transit.append(i[1])

goal_ship = set(goal_ship)
transit = set(transit)

ans = goal_ship & transit

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

Submission status: Accepted

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

first = [False for _ in range(N + 1)]
second = [False for _ in range(N + 1)]

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

    if a == 1:
        first[b] = True
    if b == 1:
        first[a] = True
    if a == N:
        second[b] = True
    if b == N:
        second[a] = True

for f, s in zip(first, second):
    if f and s:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

ninoshima=[[0]*(n+1) for i in range(2)]

for i in range(m):
    if ab[i][0]==1:
        ninoshima[0][ab[i][1]]=1
    if ab[i][1]==n:
        ninoshima[1][ab[i][0]]=1
    

for i in range(n+1):
    if ninoshima[0][i]==ninoshima[1][i]==1:
        print("POSSIBLE")
        quit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

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

slink = {}
glink = {}

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink[b] = 1
    elif b == 1:
        slink[a] = 1
    elif a == N:
        glink[b] = 1
    elif b == N:
        glink[a] = 1

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

print (ans)

Submission status: Accepted

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

s = []
e = []
for _ in range(M):
    ab = list(map(int, input().split()))
    if ab[0] == 1:
        s.append(ab[1])
    if ab[1] == N:
        e.append(ab[0])

s = set(s)
e = set(e)

t = s & e

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

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
atob = [0] * N
btoz = [0] * N
for _ in range(M):
    a, b = list(map(int,input().split()))
    if a == 1:atob[b-1] = 1
    elif a == N:btoz[b-1] = 1
    if b == 1:atob[a-1] = 1
    elif b == N:btoz[a-1] = 1

for i in range(N):
    if atob[i]*btoz[i] == 1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')

Submission status: Accepted

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

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

for i in range(m):
    a, b = map(int, (input().split()))
    graph[a] += [b]
    graph[b] += [a]

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
island=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    island[a].append(b)
    island[b].append(a)
for i in range(n+1):
    if 1 in island[i] and n in island[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    C = [0] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            C[b] += 1
        elif b == N:
            C[a] += 1
    if C.count(2) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
if m == 1:
    print("IMPOSSIBLE")
    exit()
a = set()
b = set()
for i in range(m):
    arr = list(map(int,input().split()))
    if 1 in arr:a.add(arr[1])
    if n in arr:b.add(arr[0])
if len(a&b)==0:print("IMPOSSIBLE")
else:print("POSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=[]
d=[]
for _ in range(m):
  a,b=map(int,input().split())
  if a==1:
    c.append(b)
  elif b==n:
    d.append(a)
if len(set(c)&set(d))!=0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

g = [[] for i in range(N + 1)]
for pi in p:
	g[pi[0]].append(pi[1])
	g[pi[1]].append(pi[0])

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
IN,OUT={},{}
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        if b in OUT:
            print("POSSIBLE")
            exit()
        else:IN[b]=1
    if b==n:
        if a in IN:
            print("POSSIBLE")
            exit()
        else:OUT[a]=1
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dat_m = [[] for x in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    dat_m[a].append(b)
c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True
print("POSSIBLE" if c else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
dat = deque([])
dat2 = deque([])
dat_finish = [False] * (n + 1)

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

for i in range(m):
    a, b = dat.pop()
    if b == n:
        dat_finish[a] = True

c = False
for i in range(m):
    a, b = dat2.pop()
    if a == 1:
        if dat_finish[b]:
            c = True

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
dat = deque([])
dat_finish = [False] * (n + 1)

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

for i in range(m):
    a, b = dat[i]
    if b == n:
        dat_finish[a] = True

c = False
for i in range(m):
    a, b = dat[i]
    if a == 1:
        if dat_finish[b]:
            c = True

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
dat_m = [deque([]) for x in range(n + 1)]

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

c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
dat_m = []
for i in range(n + 1):
    dat_m.append(deque([]))

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

c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True

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

Submission status: Accepted

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

A = []
B = []
buff = [0 for i in range(N+1)]
buff2 = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        # buff[b] = 1
        buff[b] = 1
    if b == N:
        B.append(a)
        buff2[a] = 1

for i in range(N+1):
    if buff[i] == 1 and buff2[i] == 1:
        print('POSSIBLE')
        exit()



# print(buff)
# print(buff2)

# seikai1 = []
# for i in range(N+1):
#     if buff[i] == 1:
#         seikai1.append(i)

# for i in range(N+1):
#     if buff2[i] == 1:
#         if i in seikai1:
#             print('POSSIBLE')
#             exit()
# for i in range(len(buff)):
#     for j in range(len(buff2)):
#         if buff[i] == 1 and buff2[j] == 1:
#             print('POSSIBLE')
#             exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dat = []
dat_m = [[]] * (n+1)
dat_finish = [False] * (n+1)

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

#print(dat)
for i in range(m):
    a,b = dat[i]
    if b == n:
        dat_finish[a] = True
#print(dat_finish)

c = False
for i in range(m):
    a,b = dat[i]
    if a == 1:
        if dat_finish[b]:
            c = True

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = set()
for _ in range(M):
    a, b = map(int, input().split())
    s.add((a, b))
result = "IMPOSSIBLE"
for m in range(2, N):
    if (1, m) in s and (m, N) in s:
        result = "POSSIBLE"
        break
print(result)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
AB = {}
ans = 'IMPOSSIBLE'
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        if b in AB:
            if AB[b] == n:
                ans = 'POSSIBLE'
                break
        else:
            AB[b] = 1


    if b == n:
        if a in AB:
            if AB[a] == 1:
                ans = 'POSSIBLE'
                break
        else:
            AB[a] = n
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

import sys
input = sys.stdin.readline

def main():
    num_land, num_ship = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num_ship)]

    move_dic = defaultdict(set)

    for i in range(num_ship):
        a, b = data[i]
        move_dic[a].add(b)
        move_dic[b].add(a)

    next_land = move_dic[1]
    for ele in next_land:
        aaa = move_dic[ele]
        if num_land in aaa:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ARC079C - Cat Snuke and a Voyage (ABC068C)
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    s, d = set(), set()
    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            s.add(b)
        elif b == n:
            d.add(a)
    print("POSSIBLE" if s & d else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ARC079C - Cat Snuke and a Voyage (ABC068C)
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().rstrip().split())
    s, d = set(), set()
    for _ in range(m):
        a, b = map(int, input().rstrip().split())
        if a == 1:
            s.add(b)
        elif b == n:
            d.add(a)
    print("POSSIBLE" if s & d else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ARC079C - Cat Snuke and a Voyage (ABC068C)
import sys
input = sys.stdin.readline

def main():
    n, m = list(map(int, input().rstrip().split()))
    s, d = set(), set()
    for _ in range(m):
        a, b = list(map(int, input().rstrip().split()))
        if a == 1:
            s.add(b)
        elif b == n:
            d.add(a)
    ans = len(s & d)
    print("POSSIBLE" if ans else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
forward = [0 for i in range(n)]
backward = [0 for i in range(n)]
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    if a == 1:
        forward[b] = 1
    elif  b == 1:
        forward[a] = 1
    elif a == n:
        backward[b] = 1
    elif b == n:
        backward[a] = 1
flag = False
for i in range(n):
    if forward[i] == 1 and backward[i] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
for i in range(1, N+1):
    if 1 in E[i] and N in E[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[map(int,input().split()) for _ in range(m)]
t1=set()
t2=set()
for a,b in ab:
    if a==1:
        t1.add(b)
    if b==n:
        t2.add(a)
for t in t1:
    if t in t2:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ls = [[int(x) for x in input().split()] for _ in range(m)]
ls1 =[]
lsn =[]


for i in range(m):
	if ls[i][0]==1:
		ls1.append(ls[i][1])
	elif ls[i][1]==1:
		ls1.append(ls[i][0])
	elif ls[i][0]==n:
		lsn.append(ls[i][1])
	elif ls[i][1]==n:
		lsn.append(ls[i][0])

if len(set(ls1)&set(lsn))!=0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Accepted

Solution code:

N,M=map(int,input().split())
t=set()
s=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        s.add(b)
    if b==N:
        t.add(a)
for i in s:
    if i in t:
        print("POSSIBLE")
        quit()
print("IMPOSSIBLE")

Submission status: Accepted

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

if len(set(li))==len(li): print('IMPOSSIBLE')
else: print('POSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

num = list(map(int,input().split()))
N = num[0]
M = num[1]

a = []
b = []

firstisland = []
islandlast = []

for i in range(M):
    num = list(map(int,input().split()))
    a.append(num[0])
    b.append(num[1])
    if (num[0] == 1):
        firstisland.append(num[1])
    if (num[1] == N):
        islandlast.append(num[0])

island = set(firstisland) & set(islandlast)

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

Submission status: Accepted

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

for i in range(M):
  if li[i][0]==1:
    s.append(li[i][1])
  else:
    break

li.sort(key=lambda x: x[1],reverse=True)

for i in range(M):
  if li[i][1]==N:
    g.append(li[i][0])
  else:
    break

if len(set(s)&set(g))>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

ato = []
bto = []

for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        ato.append(b)
    if b == N:
        bto.append(a)

ato = set(ato)
bto = set(bto)

dec = ato & bto

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

Submission status: Accepted

Solution code:
# 1からNへの経由地点Kの気持ちでみると各クエリで判別可能
n, m = map(int, input().split())
arr = [[False, False] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        arr[b - 1][0] = True
    if b == n:
        arr[a - 1][1] = True

for x in arr:
    if x[0] and x[1]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
dict=defaultdict(int)
l1=[]
l2=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        l1.append(b)
    if b==N:
        dict[a]=1
for i in l1:
    if dict[i]:
        print("POSSIBLE")
        quit()
print("IMPOSSIBLE")

Submission status: Accepted

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

islands = {}
for i in range(M):
    a,b = map(int, input().split())
    if a not in islands:
        islands[a] = {}
    if b not in islands:
        islands[b] = {}
    islands[a][b] = islands[b][a] = 1

if N not in islands:
    print('IMPOSSIBLE')
    exit()
for i in islands[1].keys():
    if i in islands[N]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[]
B=[]
for _ in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
one=[]
des=[]
for i in range(m):
    if A[i]==1:
        one.append(B[i])
    if B[i]==1:
        one.append(A[i])
for j in range(m):
    if A[j]==n:
        des.append(B[j])
    if B[j]==n:
        des.append(A[j])
one=set(one)
des=set(des)
ans=one & des
if len(ans)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

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

  l=[]
  for _ in range(m):
    a,b=LI()

    if a==1:
      l.append(b)
    elif b==n:
      l.append(a)

  x=len(l)
  y=len(list(set(l)))

  if x!=y:
    return 'POSSIBLE'
  return 'IMPOSSIBLE'

print(main())

Submission status: Accepted

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

n, m = map(int, input().split())
Island_1 = []
Island_n = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        Island_1.append(b)
    if b == n:
        Island_n.append(a)
if len(set(Island_1) & set(Island_n)) == 0:
    ans = 'IMPOSSIBLE'
else:
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
l,r = {k:False for k in range(1,n+1)},{k:False for k in range(1,n+1)}
for a,b in ab:
    if a == 1:  l[b] = True
    if b == n:  r[a] = True
for i in range(1,n+1):
    if r[i] is True and l[i] is True:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(M):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    ret = NO
    for n in conn[0]:
        if N - 1 in conn[n]:
            ret = YES
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

if len(from_one & to_n) > 0:
    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):
    a, b = map(int, input().split())
    if a == 1:
        A[b - 1] =1
    if b == N:
        B[a - 1] = 1

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

print('IMPOSSIBLE')

Submission status: Accepted

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

start = [0] * M
end = [0] * M

s_middle = []
middle_e = []

for m in range(M):
    line = list(map(int, input().split()))
    start[m] = line[0]
    end[m] = line[1]
    
    if start[m] == 1:
        s_middle.append(end[m])
    if end[m] == N:
        middle_e.append(start[m])
        
if not s_middle or not middle_e:
    print('IMPOSSIBLE')
    sys.exit()

if set(s_middle) & set(middle_e):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

#訪れることができるかのリスト
lst = [0] * N

flag = False #フラグを立てる
for i in range(M): #M種の定期船について確認
    a, b = map(int,input().split())
    if a == 1: #スタートが1の時
        if lst[b-1] == 1: #Nから1回で来る船があるならOK
            flag = True
        else:
            lst[b-1] = 1 #Nから1回で来る船がない時、1からは1回で来れることをメモ
    if b == N: #ゴールがNの時
        if lst[a-1] == 1: #1から1回で来る船があるならOK
            flag = True
        else:
            lst[a-1] = 1 #1から1回で来る船がない時、Nからは1回で来れることメモ

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

Submission status: Accepted

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

lst = [0] * N

flag = False
for i in range(M):
    a, b = map(int,input().split())
    if a == 1:
        if lst[b-1] == 1:
            flag = True
        else:
            lst[b-1] = 1
    if b == N:
        if lst[a-1] == 1:
            flag = True
        else:
            lst[a-1] = 1

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  d[a-1].add(b-1)
  d[b-1].add(a-1)
f=False
for x in d[0]:
  if n-1 in d[x]:
    f=True
    break
print('POSSIBLE' if f else 'IMPOSSIBLE')

Submission status: Accepted

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

def main():
    n = N
    s = []
    g = []
    for m in range(M):
        a, b = [int(s) for s in input().split()]
        if a == 1:
            s.append(b)
        if b == n:
            g.append(a)
    ans = 'POSSIBLE' if len(set(s) & set(g)) > 0 else 'IMPOSSIBLE'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("POSSIBLE")
    elif q == 0:print("IMPOSSIBLE")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
#これを消すとなぜかWAになる呪い
right = set()
left = set()
for i in range(m):
    a = [int(i) for i in input().split()]
    if a[0] == 1:
        right.add(a[1])
    elif a[1] == n:
        left.add(a[0])
right = right & left
if len(right):j(1)
j(0)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[set(map(int,input().split())) for _ in range(m)]
S=set()
G=set()
for x in l:
	if 1 in x:S.add(max(x))
	elif n in x:G.add(min(x))
S=sorted(S)
G=sorted(G)
i=0
Glen=len(G)
for x in S:
	if i==Glen:break
	elif G[i]<x:
		while i<Glen and G[i]<x:
			i+=1
	if i<Glen and x==G[i]:
		print('POSSIBLE')
		exit()
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:
# coding: utf-8
# Your code here!

import sys

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

memo = [[0, 0] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().rstrip().split(' '))
    a -= 1
    b -= 1
    
    if a == 0:
        memo[b][0] = 1
    elif b == N-1:
        memo[a][1] = 1
        
for i in range(N):
    if memo[i][0] == 1 and memo[i][1] == 1:
        print('POSSIBLE')
        sys.exit()
        
print('IMPOSSIBLE')

Submission status: Accepted

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

connect_to_1 = []
connect_to_N = []
for i in range(M):
  if edges[i][0] == 1:
    connect_to_N.append(edges[i][1])
  if edges[i][1] == N:
    connect_to_1.append(edges[i][0])

if len(set(connect_to_1) & set(connect_to_N)) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict
N ,M = list(map(int,input().split(" ")))
di = defaultdict(lambda :[])
for _ in range(M):
    a,b = list(map(int,input().split(" ")))
    di[a].append(b)
    di[b].append(a)
ans = "IMPOSSIBLE"
for v in di.values():
    if 1 in v and N in v:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
startlist = [False]
goallist = [False]
for i in range(0, N):
	startlist.append(False)
	goallist.append(False)
for i in range(0, M):
	a, b = map(int, input().split())
	if a == 1: startlist[b] = True
	if b == N: goallist[a] = True
ans = 'IMPOSSIBLE'
for i in range(0, N+1):
	if startlist[i] and goallist[i]:
		ans = 'POSSIBLE'
		break
print(ans)

Submission status: Accepted

Solution code:

n, m = [ int(v) for v in input().split() ]
first_ship = []
second_ship = []

for i in range(m):
	start, end = [ int(v) for v in input().split() ]
	if start == 1:
		first_ship.append(end)
	if end == n:
		second_ship.append(start)

if len(set(first_ship+second_ship)) == len(first_ship) + len(second_ship):
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

Submission status: Accepted

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

# print(land)
ans = "IMPOSSIBLE"
for l in land[0]:
	if n-1 in land[l]:
		ans = "POSSIBLE"
		break
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n,m=LI()
  
  l=[]
  for _ in range(m):
    a,b=LI()

    if a==1:
      l.append(b)
    elif a==n:
      l.append(b)
    elif b==n:
      l.append(a)

  if len(l)!=len(list(set(l))):
    return 'POSSIBLE'

  return 'IMPOSSIBLE'

print(main())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
C = set()
D = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        C.add(b)
    if b == 1:
        C.add(a)
    if a == N:
        D.add(b)
    if b == N:
        D.add(a)
print('POSSIBLE' if C & D else 'IMPOSSIBLE')

Submission status: Accepted

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

for i in range(m):
    ta,tb = map(int, input().split())
    if not ta in a:
        a[ta] = [tb]
    else:
        a[ta].append(tb)

ans=False
for i in a[1]:
    if not i in a: continue
    if n in a[i]:
        ans = True
        
print(("IMPOSSIBLE","POSSIBLE")[ans])

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
e=[[]for i in range(n+1)]
for a,b in zip(t[1::2],t[2::2]):
  e[a].append(b)
  e[b].append(a)
i=0
for v in e[1]:
  for w in e[v]:
    if w==n:
      i=2
print('IMPOSSIBLE'[i:])