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: Runtime Error

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

for (i,j) in ab:
  if i in mi and j==n:
    print("POSSIBLE");exit()
    
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]

a = sorted(li,key = lambda x:-x[1])


for i in range(m):
    if a[i][1] < n:
        break
    else:
        c.append(a[i][0])

a = sorted(li,key = lambda x:x[0])
for i in range(m):
    if a[i][0] > 1:
        break
    if a[i][1] in c:
            print("POSSIBLE")
            sys.exit()
        
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
# N: 島の数
# M: 定期便のルート
N, M = input().split()

a = []
b = []
# 船のルートを記録
for m in range(int(M)):
    _a, _b = input().split()
    a.append(_a)
    b.append(_b)


if a.index("1") !=False:
    for i in a.index("1"):
        if b.index(N) !=False:
            for l in b.index(N):
                if a[l] != b[i]:
                    continue
                else:
                    if int(b[l]) == N:
                        print("POSSIBLE")
                        sys.exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
li = []
numb = []
ans = ''
for i in range(M):
  a,b = map(int,input().split())
  if a == 1:
    li.append(b)
  elif b == N:
    numb.append(a)
for i in range(M):
  if li[i] in numb:
    ans = 'POSSIBLE'
    break
if ans == '':
  print('IMPOSSIBLE')
else:
  print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
li = []
numb = []
ans = ''
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        li.append(b)
    elif b == N:
        numb.append(a)
for i in range(M):
  if li[i] in numb:
    ans = 'POSSIBLE'
    break
if ans == '':
  print('IMPOSSIBLE')
else:
  print(ans)

Submission status: Runtime Error

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

L=[[0]*2 for i in range(M)]

for i in range(M):
    L[i][0] , L[i][1] = map(int, input().split())

A=[0]*M
B=[0]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break
A=A[0:i]

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break
B=B[0:i]

if((max(A)<min(B))or(max(B)<min(A))):
        print("IMPOSSIBLE")
        exit()

for i in B:
    if i == 10**10 : 
        print("IMPOSSIBLE")
        exit()
    if i in A:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N,M = list(map(int,input().split()))
x = 1
y = 1

for m in M:
    a,b = list(map(int,input().split()))
    if a==1:
      x|=1<<b
    if b==N:
      y|=1<<a

print("IM"*(x&y==1)+"POSSIBLE")

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
import numpy as np
g = np.zeros((n+1, n+1))
for _ in range(m):
    a, b = map(int, input().split())
    g[a][b] = 1
    g[b][a] = 1
ans = "IMPOSSIBLE"
for i in range(n+1):
    if g[1][i] == 1:
        if g[i][n] == 1:
            ans = "POSSIBLE"
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
path = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in path:
        path[a] = [b]
    else:
        path[a].append(b)

ns = []
if 1 in path:
    for p in path[1]:
        ns.append(p)

    flag = False
    for mid in ns:
        if n in path[mid]:
            flag = True
            break

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

else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
path = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in path:
        path[a] = [b]
    else:
        path[a].append(b)

ns = []
for p in path[1]:
    ns.append(p)

flag = False
for mid in ns:
    if n in path[mid]:
        flag = True
        break

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

Submission status: Runtime Error

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

li=[[] for i in range(m+1)]

for a,b in ab:
    li[a].append(b)

li2=[]
for i in li[1]:
    li2.append(i)

ans=False
for i in li2:
    if n in li[i]:
        ans=True
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
A = []
B = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        B.append(b)
    if b == N:
        A.appned(a)
for a in A:
    if a in B:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
edges = {}
flag = 'IMPOSSIBLE'
for a, b in AB:
    if a in edges:
        edges[a].append(b)
    else:
        edges[a] = [b]
for i in edges[1]:
    if N in edges[i]:
        flag = 'POSSIBLE'
        break

print(flag)

Submission status: Runtime Error

Solution code:
def dfs(now,prev,count):
    global flag
    flag=False
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if next != prev:
            if next== n-1:
                if count==2:
                    flag=True
                    break
                else:
                    break
            dfs(next, now,count)
 
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)
dfs(0,-1,0)
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
def dfs(now,prev,count):
    global flag
    flag=False
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if next != prev:
            if next== n-1:
                if count==2:
                    flag=True
                    break
                else:
                    break
            dfs(next, now,count)
 
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)
dfs(0,-1,0)
if flag:
    print('POSSIBBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
def dfs(now,prev,count):
    global flag
    flag=False
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if next != prev:
            if next== n-1:
                if count==2:
                    flag=True
                    break
                else:
                    break
            dfs(next, now,count)
 
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)
dfs(0,0,0)
if flag:
    print('POSIBBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc068/tasks/arc079_a
# C - Cat Snuke and a Voyage

n, m = list(map(int, input().split()))
ab_list = []

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

ab_dict = {k: [] for k in range(1, m+1)}

for a, b in ab_list:
    # 子供を覚えさせる
    ab_dict[a].append(b)

next_node_list = ab_dict[1]
# 来訪済の島
done_list = []
done_list.append(1)

def search(node_list):
    for node in node_list:
        if node == n:
            return True

    return False

# 深さ優先探索
for node in next_node_list:
    if node not in ab_dict.keys():
        # 行き止まり
        is_ok = False
        continue

    if node == n:
        is_ok = True
    else:
        is_ok = search(ab_dict[node])
    if is_ok:
        break

ans = 'POSSIBLE' if is_ok else 'IMPOSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(M))
    S, D = set(), set()  # start, destination
    for a, b in E:
        if a == 1:
            S |= {b}
        if b == N:
            D |= {a}
    flg = S & D  # if the same X in both S & D -> possible
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

ans = "IMPOSSIBLE"
second_island = []

for a, b in ab_list:
  if a == 1:
    second_island.append(b)

  if b == N:
	if a in second_island:
      ans = "POSSIBLE"
      break

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [(lambda x, y:(x, y))(*map(int, input().split())) for _ in range(m)]
d = {}
for x in ab:
  if x[0] in d.keys():
    d[x[0]].append(x[1])
  else:
    d[x[0]] = [x[1]]
moyo = []
for z in d[1]:
  moyo += d[z]
for z in moyo:
  if z == n:
    exit(print('POSSIBLE'))
print('IMPOSSIBLE')

Submission status: Runtime Error

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

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

print ("POSSIBLE" if D[D[1]] == N else "IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = [x for x in input().split()]
E = [[] for x in range(N+1)]
visited = set()

for i in range(M):
    A, B = [x for x in input().split()]
    E[A].append(B)
    E[B].append(A)

if E[1] & E[N]:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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: Runtime Error

Solution code:
N, M = map(int, input().split())
ships = [[]] * (2*10**5+1)
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  for _dist in ships[_to]:
  	if _dist == N:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ships =　[[]] * (2*10**5+1)
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  if _to == N:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

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: Runtime Error

Solution code:
N,M=map(int,input().split())
onetox=[]
xtoN=[]
ans="IMPOSSIBLE"
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        onetox.append(b)
    if b==N:
        xtoN.append(a)
    if len(onetox & xtoN)>0:
        ans="POSSIBLE"
        break
print(ans)

Submission status: Runtime Error

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 a[i]*b[i] == 1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')

Submission status: Runtime Error

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: Runtime Error

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

Submission status: Runtime Error

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(c&d)!=0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

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))

dat2 = dat.copy()

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: Runtime Error

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: Runtime Error

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

for i in one:
  if i in enu:
    flag=true

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

Submission status: Runtime Error

Solution code:
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: Runtime Error

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 x==G[i]:
		print('POSSIBLE')
		exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

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=S+x
	elif n in x:G=G+x
print('POSSIBLE' if len(S&G)>0 else 'IMPOSSIBLE')

Submission status: Runtime Error

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


import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False
cnt = 0
ab2 = [[0]] * (N+1)
for j in range(M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
for i in ab[1][1:]:
    q.put(i)
    cnt += 1
idx = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if idx < cnt:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    idx += 1
print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
flag=False
for i in g[1]:
  for j in i:
    if j==n:
      flag=True
if flag==True:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
keys = [0]*M
values = [0]*M
a = {}
for i in range(M):
    keys[i], values[i]= map(int, input().split())
a.update(zip(keys, values))
for i in range(M):
    if 1 in keys and N in values:
        a_one = a[1]
        if a[a_one] == N:
            print('POSSIBLE')
            exit()
    else:
        break
print('IMPOSSIBLE')

Submission status: Runtime Error

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

A1 = [1]
B4 = [4]
for i in range(M):
    if AB[i][0] == 1:
        A1.append(A[i][1])
    if AB[i][1] == N:
        B4.append(A[i][0])

ans = 'IMPOSSIBLE'
for a in A1:
    if a in B4:
        ans = 'POSSIBLE'

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
one = [0 for i in range(n)]
ans = "IMPOSSIBLE"
for i in a:
  if i[0] == 1:
    if one[i[1]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[1]] = 1
  elif i[1] == n:
    if one[i[0]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[0]] = 1
print(ans)

Submission status: Runtime Error

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

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

        
for i in ship.keys():
  if n in ship[i]:
    print("POSSIBLE")
    exit()
  else:
    for j in ship[i]:
      if n in ship[j]:
        print("POSSIBLE")
        exit()
      

  
  
print("IMPOSSIBLE")

Submission status: Runtime Error

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while a[x][0]== 1 and x < m:
    li_a.append(a[x][1])
    x += 1

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

x = 0
li_b = []

while a[x][1] == n and x < m:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")

Submission status: Runtime Error

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while a[x][0]== 1 and x < n:
    li_a.append(a[x][1])
    x += 1

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

x = 0
li_b = []

while a[x][1] == n and x < n:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import itertools

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while a[x][0]== 1:
    li_a.append(a[x][1])
    x += 1

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

x = 0
li_b = []

while a[x][1] == n:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
ab_a = sorted(ab)
ab_b = sorted(ab, key= lambda x:x[1])

way = [0] * (n + 1)
for a, b in ab:
    if a == 1:
        way[b] += 1
    if b == 1:
        way[a] += 1
    if a == n:
        way[b] += 1
    if b == n:
        way[a] += 1
if 2 in way:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
def input():
    return sys.stdin.readline()
n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
c=[0]*(n+1)
f1=[]
f2=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        c[b[i]]=1

ans='IMPOSSIBLE'
for i in range(m):
    if b[i]==n:
        if c[a[i]]==1:
            ans='POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
def input():
    return sys.stdin.readline()
n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
f1=[]
f2=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        f1.append(b[i])
    if b[i]==n:
        f2.append(i)
        

ans='IMPOSSIBLE'
for i in f2:
    if a[i] in f1:
        ans='POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
f1=[]
f2=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        f1.append(b[i])
    if b[i]==n:
        f2.append(i)
        

ans='IMPOSSIBLE'
for i in f2:
    if a[i] in f1:
        ans='POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:

n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
pos=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        pos.append(b[i])

ans='IMPOSSIBLE'
for i in range(m):
    if b[i]==n:
        if a[i] in pos:
            ans='POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:

N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
dist = [INF]*(N)
for i in range(M):
    if ab[i][0] == 1:
        dist[ab[i][1]-1] = 1
for i in range(M):
    if ab[i][1] == N:
        if dist[ab[i][0]-1] <= 1:
            print("POSSIBLE")
            exit()
        else:
            continue
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)

    q = deque()
    q.append(*A[1])

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
one = []
nnn = []
for i in range(M):
    ai,bi = map(int,input().split())
    if ai == 1:
        one.append(bi)
    if bi == N:
        nnn.append(ai)
def bs_left(l, target): # l=sorted, target以上の値をもつ要素のうち一番左のindexを返す
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if l[mid] < target:
            low = mid+1
        else:
            high = mid
    return low
flag = False
if len(one) == 0 or len(nnn) == 0:
    pass
else:
    nnn.sort()
    for i in range(len(one)):
        if nnn[bs_left(nnn,one[i])] == one[i]:
            flag = True
            break

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
g=0
ListA=[]
ListB=[]
for i in range(0,M,1):
  a,b=map(int,input().split())
  ListA.append(a)
  ListB.append(b)

ListC=[]
c=ListA.count(1)
for i in range(0,c,1): #ListCに1からの行き先を入れる
  d=ListA.find(1)
  ListA.pop(d)
  ListA.insert(d,0)
  ListC.append(d)

for i in range(0,len(ListC),1):
  e=ListC[i]
  f=ListB[e]
  if f==N:
    g=1
    break
  else:
    g=0
    continue

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
g=0
ListA=[]
ListB=[]
for i in range(0,M,1):
  a,b=map(int,input().split())
  ListA.append(a)
  ListB.append(b)

ListC=[]
c=ListA.count(1)
for i in range(0,c,1): #ListCに1からの行き先を入れる
  d=ListA.find(1)
  ListA.pop(d)
  ListA.insert(d,0)
  ListC.append(d)

for i in range(0,len(ListC),1):
  e=ListC[i]
  f=ListB[e]
  if f==N:
    g=1
    break
  else:
    g=0
    continue

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

Submission status: Runtime Error

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

s = [0]*n
g = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] = 1
    if b == n:
        g[a] = 1
for i in range(n):
    if s[i] and g[i]:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

mat = np.zeros((n,n))
for x in ab:
    mat[x[0]][x[1]] = 1
    mat[x[1]][x[0]] = 1
vec = np.zeros(n)
vec[0] = 1
vec[-1] = 1
if list(mat.dot(vec)).count(2) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

e = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    e[a] += 1
  elif(b == N):
    e[b] += 1
if(2 in e):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
n,m = LI()
v = [[] for i in range(n)]
for i in raneg(m):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
bfs_map = [-1 for i in range(n)]
bfs_map[0] = 0
q = deque()
q.append(0)
while q:
    x = q.pop()
    for y in v[x]:
        if bfs_map[y] == -1:
            bfs_map[y] = bfs_map[x] + 1
            q.append(y)
if bfs_map[y] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
n,m = LI()
v = [[] for i in range(n)]
for i in raneg(m):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
bfs_map = [-1 for i in range(n)]
bfs_map[0] = 0
q = deque()
q.append(0)
while q:
    x = q.pop()
    for y in v[x]:
        if bfs_map[y] == -1:
            bfs_map[y] = bfs_map[x] + 1
if bfs_map[y] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

Solution code:
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = []
for i in range(M):
  a,b = IL()
  if a == 1:
    if b in data:
      print("POSSIBLE")
      break
    else:
      data.append(b)
  if b == N:
    if a in data:
      print("POSSIBLE")
      break
    else:
      data.append(a)
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

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

ab.sort()
data = []
for a,b in ab:
  if a == 1:
    data.append(b)
  else:
    break

for i in range(M,-1,-1):
  a = ab[i][0]
  if a in data and ab[i][1] == N:
    print("POSSIBLE")
    break
  elif a==1:
    print("IMPOSSIBLE")
    break

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
N=int(input())
a=list(map(int,input().split()))

ans=''
for i in range(N):
    ans+=str(i+1)*a[i]

for j in range(H):
    s=ans[W*j:W*(j+1)]
    if j%2==0:
        print(' '.join(s))
    else:
        print(' '.join(s[::-1]))