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())
s = [list(map(int,input().split())) for i in range(m)]
nl = [[] for i in range(n+1)]
for a,b in s: nl[a].append(b
can = False
for i in range(2,n):
    if i in nl[1] and n in nl[i]: can = True 
ans = "POSSIBLE" if can else "IMPOSSIBLE"
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edges=[[]for i in range(n)]
visited=[False]*n
cnt=0
def dfs(u,cnt,visited):
  visited=visited[:]
  cnt=cnt
  visited[u]=True
  if visited[-1]==True:
    return cnt,visited
  cnt+=1
  for v in edges[u]:
    if visited[v]==False:
      dfs(v,cnt,visited)
  return cnt,visited

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

cnt,visited=dfs(0)
if visited[-1]==True and cnt==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edges=[[]for i in range(n)]
visited=[False]*n
cnt=0
def dfs(u):
  global visited
  global cnt
  visited[u]=True
  if visited[-1]==True:
    return cnt,visited
  cnt+=1
  for v in edges[u]:
    if visited[v]==False:
      dfs(v)
  return cnt,visited

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

cnt,visited=dfs(0)
if visited[-1]==True and cnt==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edges=[[]for i in range(n)]
visited=[False]*n
cnt=0
def dfs(u):
  global visited
  global cnt
  visited[u]=True
  if visited[-1]==True:
    return cnt,visited
  cnt+=1
  for v in edges[u]:
    if visited[v]==False:
      dfs(v)
  return visited,cnt

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

visit,cnt=dfs(0)
if visit[-1]==True and cnt==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import bisect
n, m = map(int, input().split())
AB = [[int(i) for i in input().split()] for i in range(m)]
S = []
G = []

for ab in AB:
    if ab[0] == 1:
        S.append(ab[1])
    if ab[1] == n:
        G.append(ab[0])

S.sort()
G.sort()
        
ans = 'IMPOSSIBLE'
if len(S) != 0 and len(G) != 0:
    for s in S:
        idx = bisect.bisect_left(G, s)
        if s == G[idx]:
            ans = 'POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n, m = map(int, input().split())
AB = [[int(i) for i in input().split()] for i in range(m)]
S = []
G = []

for ab in AB:
    if ab[0] == 1:
        S.append(ab[1])
    if ab[1] == n:
        G.append(ab[0])

S.sort()
G.sort()
        
ans = 'IMPOSSIBLE'
if len(G) != 0:
    for s in S:
        idx = bisect.bisect_left(G, s)
        if s == G[idx]:
            ans = 'POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n, m = map(int, input().split())
AB = [[int(i) for i in input().split()] for i in range(m)]
S = []
G = []

for ab in AB:
    if ab[0] == 1:
        S.append(ab[1])
    if ab[1] == n:
        G.append(ab[0])
        
ans = 'IMPOSSIBLE'
if len(G) != 0:
    for s in S:
        idx = bisect.bisect_left(G, s)
        if s == G[idx]:
            ans = 'POSSIBLE'
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m=map(int,input().split())
nextmatrix=np.zeros((n,n))
for i in range(m):
    a,b=map(int,input().split())
    nextmatrix[a-1][b-1]=1
    nextmatrix[b-1][a-1]=1
nextmatrix2=nextmatrix.dot(nextmatrix)
if nextmatrix2[0][n-1]==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Runtime Error

Solution code:
#068-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import numpy as np
n,m=IL()
nm=np.zeros((n,n))
for i in range(m):
    a,b=IL()
    nm[a-1][b-1]=1
    nm[b-1][a-1]=1
nm=nm.dot(nm)
if nm[0][n-1]==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)
    min_len=0
    while max_len>=min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif li[mid]<a:
            min_len=mid+1
        else:
            max_len=mid-1
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort()
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)
    min_len=0
    while max_len>min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif abs(min_len-max_len)==1 and li[min_len]!=a and li[max_len]!=a:
            break
        elif li[mid]<a:
            min_len=mid
        else:
            max_len=mid
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)
    min_len=0
    while max_len>min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif abs(min_len-max_len)==1 and li[mid]!=a and li[mid+1]!=a and li[mid-1]!=a:
            break
        elif li[mid]<a:
            min_len=mid
        else:
            max_len=mid
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

hune1 = []
hune2 = []
for keiro in hunes:
  keiro.sort()
  if keiro[0] == 1:
    hune1.append(keiro)
  if keiro[1] == n:
    hune2.append(keiro)

possible = []
for i in hune1:
  for j in hune2:
    if i[1] == j[0]:
      print("POSSIBLE")
      ikeru.append(1)
if len(possible) == 0:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

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

if len(intersect_list(one, two)) != 0:
    print("POSSIBLE")

else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

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



for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")  
                break
    if flag == 1:
        break

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

Submission status: Runtime Error

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        

###
#for i in range(len(one)):
#    for j in range(len(two)):
#        if one[i] == two[j]:
#            flag = 1
#            print("POSSIBLE")
#            break
#    if flag == 1:
#        break
###
if flag == 0:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect

n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
f_1.sort()
t_n.sort()
for i in range(len(f_1)):
    p = bisect.bisect_left(t_n, f_1[i])
    if p != len(t_n)-1 and f_1[i] == t_n[p+1]:
        jedge = 1
        break
    elif p == len(t_n)-1 and f_1[i] == t_n[p]:
        jedge = 1
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect

n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
f_1.sort()
t_n.sort()
for i in range(len(f_1)):
    p = bisect.bisect_left(t_n, f_1[i])
    if p != len(t_n) and f_1[i] == t_n[p+1]:
        jedge = 1
        break
    elif p == len(t_n) and f_1[i] == t_n[p]:
        jedge = 1
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect

n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
f_1.sort()
t_n.sort()
for i in range(len(f_1)):
    p = bisect.bisect_left(t_n, f_1[i])
    if f_1[i] == t_n[p]:
        jedge = 1
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect

n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
f_1.sort()
t_n.sort()
for i in range(len(f_1)):
    p = bisect.bisect_left(t_n, f_1[i])
    if f_1[i] == t_n[p+1]:
        jedge = 1
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) or j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<m or j<m:
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<n or j<n:
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
p=[]
q=[]
n,m = map(int,input().spplit())
for _ in [0]*m:
  a,b = map(int,input().spplit())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
for x in p:
  if x in q:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
mid, las = [], []
ans = 0

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

if set(mid) & set(las) != 0:
    ans = 1　

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Runtime Error

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

for i in range(M):
    if ab[i][0] == 1:
        tyukan.append(ab[i][1])

for i in ab:
    if ab[i][0] in tyukan:
        if ab[i][1] == N:
            ans =1
            break

print('POSSIBLE' if ans == 1 else 'INPOSSIBLE')

Submission status: Runtime Error

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
first = set()
second = set()

for l in line:
    if end in l:
        second.add(l[0])
        second.add(l[1])
    elif start in l:
        first.add(l[1])
        first.add(l[0])
first.remove(start)
second.remove(end)

for f in first:
    if f in second:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
X = [0] * N
Y = [0] * N
for i in range(M):
    S, E = list(map(int, input().split()))
    if S == 1:
        X[E-1] = 1
    if E == N:
        Y[S-1] = 1
for i in range(N):
    if X[i] = Y[i]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
s1 = raw_input().split(' ')
n, m = int(s1[0]), int(s1[1])
i2il = {}
for _ in range(m):
    s = raw_input().split(' ')
    if s[0] in i2il:
        i2il[s[0]].append(s[1])
    else:
        i2il[s[0]] = [s[1]]
    if s[1] in i2il:
        i2il[s[1]].append(s[0])
    else:
        i2il[s[1]] = [s[0]]
if '1' not in i2il or s1[1] not in i2il:
    print 'IMPOSSIBLE'
else:
    mid = i2il[1]
    bhit = False
    for m in mid:
        if s1[1] in m:
            print 'POSSIBLE'
            bhit = True
            break
    if not bhit:
        print 'IMPOSSIBLE'

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append(a)
  if a == 1:
    first.append(b)
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  firsti = 0
  secondi = 0
  while(end == True):
    if first[firsti] == second[secondi]:
      print("POSSIBLE")
      break
    elif first[firsti] < second[secondi]:
      firsti += 1
      if firsti > len(first) - 1:
        print("IMPOSSIBLE")
        break
    else:
      second += 1
      if secondi > len(second) - 1:
        print("IMPOSSIBLE")
        break

Submission status: Runtime Error

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

siCheck = [0 for i in range(N)]
inCheck = [0 for i in range(N)]

for i in range(N):
    if a[i][0] == '1':
        siCheck[int(a[i][1])-1] = True
    else:
        siCheck[int(a[i][1])-1] = False
    if int(a[i][1]) == N:
        inCheck[int(a[i][0])-1] = True
    else:
        inCheck[int(a[i][0])-1] = False

for i in range(N):
    if siCheck[i] and inCheck[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Runtime Error

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

siCheck = [0 for i in range(N)]
inCheck = [0 for i in range(N)]

for i in range(M):
    if a[i][0] == '1':
        siCheck[int(a[i][1])-1] = True
    else:
        siCheck[int(a[i][1])-1] = False
    if int(a[i][1]) == N:
        inCheck[int(a[i][0])-1] = True
    else:
        inCheck[int(a[i][0])-1] = False

for i in range(M):
    if siCheck[i] and inCheck[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
N,M=map(int,input().split())
grid = []
for i in range(N):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
pre = []
pos = []
for ships in grid:
  if ships[0] == 1:
    pre.append(ships[1])
  if ships[1] == N:
    pos.append(ships[0])
pre.sort()
for islands in pre:
  if islands in pos:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections
da = list(map(int,input().split()))
a[] = []
b[] = []
for i in range(da[1]):
  k[i] = list(map(int,input().split()))
  
for i in range(da[1]):
  if k[i][0] == 1 or k[i][1] == 1:
    a.append(k[i])

for i in range(da[1]):
  if k[i][0] == da[0]or k[i][1] == da[0]:
    b.append(k[i])
    
a = list(set(a))
b = list(set(b))
 
for i in range(len(a)):
  b.append(a[i])
c = collections.Counter(b)
 
for i in range(len(c)):
  if c[i][1] >1:
    print("POSSIBLE")
    break
  else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import collections
da = list(map(int,input().split()))
a[] = []
b[] = []
for i in range(da[1]):
  k[i] = list(map(int,input().split()))
  
for i in range(da[1]):
  if k[i][0] == 1 or k[i][1] == 1:
    a.append(k[i])
 
for i in range(da[1]):
  if k[i][0] == da[0]or k[i][1] == da[0]:
    b.append(k[i])
    
a = list(set(a))
b = list(set(b))
 
k = a+b
c = collections.Counter(k)
 
for i in range(len(c)):
  if c[i][1] >1:
    print("POSSIBLE")
    break
  else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import collections
da = list(map(int,input().split()))
a[] = []
b[] = []
for i in range(da[1]):
  k[i] = list(map(int,input().split()))
  
for i in range(da[1]):
  if k[i][0] == 1 or k[i][1] == 1:
    a.append(k[i])

for i in range(da[1]):
  if k[i][0] == da[0]or k[i][1] == da[0]:
    b.append(k[i])
    
a = list(set(a))
b = list(set(b))

k = a+b
c = collections.Counter(k)

for i in range(len(c)):
  if c[i][1] >1:
    print("POSSIBLE")
    break
  else
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

for i in range(m):
  p[i]=[int(i) for i in input().split()]
  
  
#隣接リスト  
l = [[] for i in range(n+1)]
for pi in p:  #0-originedに注意、l[0]は空
        l[pi[0]].append(pi[1])
        l[pi[1]].append(pi[0])  

count=0
for i in l[1]:
  if i in l[n]:
    count=1
    
if count==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

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


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

Submission status: Runtime Error

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

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

aaa = 0
for i in tbin_1:
    if i in tbin_n:
        aaa = 1
        break

if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

tbin_2 = []
for i in range(len(tbin_o)):
    if tbin_o[i][0] == 1 or tbin_o[i][1] == n:
        tbin_2.append(tbin_o[i])

aaa = 0
for j in range(len(tbin_2)):
    for l in range(len(tbin_2)):
        if tbin_2[j][1] == tbin_2[l][0] and j != l:
            aaa = aaa + 1
            break
            
if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

tbin_2 = []
for i in range(len(tbin_o)):
    if tbin_o[i][0] == 1 or tbin_o[i][i] == n:
        tbin_2.append(tbin_o[i])

aaa = 0
for j in range(len(tbin_2)):
    for l in range(len(tbin_2)):
        if tbin_2[j][1] == tbin_2[l][0] and j != l:
            aaa = aaa + 1
            break
            
if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
x.sort()
a = []
for i in x:
	if i[0]==1:
		a.append(i[1])
	else:
		break
for j in a:
	if [j,n] in x:
		m = 0
		print("POSSIBLE")
		break
if m != 0:
	print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  if(x==n-1 and dis[x]==2):
    print("POSSIBLE")
    sys.exit()
  elif(x==n-1 and dis[x]!=INF):
    print("INPOSSIBLE")
    sys.exit()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
from collections import defaultdict

d = defaultdict([0])
goal, n = map(int, input().split())
for _ in range(n):
  f, t = map(int, input().split())
  d[f].append(t)
  d[t].append(f)
for current in d[1]:
  if goal in d[current]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
from collections import defaultdict

d = defaultdict([])
goal, n = map(int, input().split())
for _ in range(n):
  f, t = map(int, input().split())
  d[f].append(t)
  d[t].append(f)
for current in d[1]:
  if goal in d[current]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import defaultdict from collections

d = defaultdict([])
goal, n = map(int, input().split())
for _ in range(n):
  from, to = map(int, input().split())
  d[from].append(to)
  d[to].append(from)
for current in d[1]:
  if goal in d[current]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import defaultdict from collections

d = defaultdict([])
goal, n = map(int,  input().split())
for _ in range(n):
  from, to = map(int, input().split())
  d[from].append[to]
  d[to].append[from]
for current in d[1]:
  if goal in d[current]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = int(input())
set_a, set_b = set(), set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        set_a.add(b)
    if b == N:
        set_b.add(a)

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

Submission status: Runtime Error

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

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

ans = "IMPOSSIBLE"

ls = {}
f = [False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    ls[a-1] = b-1
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        f[a-1] = True

for m in range(M):
    if ans == "POSSIBLE":
        beak
    if f[m] and ls[m] in ls and  ls[ls[m]] == N-1 :
        ans = "POSSIBLE"

print(ans)

Submission status: Runtime Error

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

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

ans = "IMPOSSIBLE"

ls = {}
f = [False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    ls[a-1] = b-1
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        f[a-1] = True

for m in range(M):
    if ans == "POSSIBLE":
    if f[m] and ls[m] in ls and  ls[ls[m]] == N-1 :
        ans = "POSSIBLE"

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a={}
b={}
for i in range(M):
    k,l=map(int, input().split())
    if k==1:
        a.add(k)
    if l==N:
        b.add(l)
if a&b:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
a={}
b={}
for i in range(M):
    k,l=map(int, raw_input().split())
    if k==1:
        a.add(k)
    if l==N:
        b.add(l)
if a&b:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
a={}
b={}
for i in range(M):
    k,l=map(int, raw_input().split())
    if k==1:
        a.add(k)
    if l==1: 
        b.add(l)
if a&b: 
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
a={}
b={}
for i in range(M):
    k,l=a.append(map(int, raw_input().split()))
    if k==1:
        a.add(k)
    if l==1: 
        b.add(l)
if a&b: 
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

ans = "IMPOSSIBLE"

ls = [[] for m in range(M)]
for m in range(M):
    a,b = map(int,(input().split()))
    ls[m].append(a-1)
    ls[m].append(b-1)
    
    if a-1 == 0 and b == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        ls[m].append("P")
    else:
        ls[m].append("I")

for m in range(M):
    if ls[m][2] == "P" and ls[ls[m][1]][1] == N-1:
        ans = "POSSIBLE"

print(ans)