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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == N:
        d = d + [a]

c.sort()
d.sort()

j, k = 0, 0
for i in range(1, N):
    if (j > len(c)) or (k > len(d)):
        print("IMPOSSIBLE")
        break

    if c[j] == d[k]:
        print("POSSIBLE")
        break
    elif c[j] > d[k]:
        k = k+1
    else:
        j = j+1

Submission status: Runtime Error

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == N:
        d = d + [a]

c.sort()
d.sort()

j, k = 0, 0
for i in range(1, N):
    if (i > len(c)) or (j > len(d)):
        print("IMPOSSIBLE")
        break

    if c[j] == d[k]:
        print("POSSIBLE")
        break
    elif c[j] > d[k]:
        k = k+1
    else:
        j = j+1

Submission status: Runtime Error

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

ab = []
for i in range(0, M):
    ab = ab + list(map(int, input().split(" ")))


c = list(map(lambda y: y[1], filter(lambda x: x[0] == 1, ab)))
d = len(filter(lambda y: y[0] in c, filter(lambda x: x[1] == N, ab)))

if d > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

N, M = input().split()
islands = []
for i in range(int(M)):
    islands.append(map(int, input().split()))

print(str(islands))

first = []
second = []

for node in islands:
    if (node[0] == 1):
        first.append(node)
    if (node[1] == N):
        second.append(node)

isPosiible = False
for first_node in first:
    for second_node in second:
        if (first_node[1] == second_node[0]):
            isPosiible = True
            break

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

Submission status: Runtime Error

Solution code:
def solve(n, m, a, b):
    islands = sets()

    for i in range(m):
        if(a[i] == 1):
            islands.append(b[i])
        if(b[i] == 1):
            islands.append(a[i])

    for i in range(m):
        if(a[i] == n and b[i] in islands):
            return "POSSIBLE"
        if(b[i] == n and a[i] in islands):
            return "POSSIBLE"
    return "IMPOSSIBLE"

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

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

print(solve(n, m, a, b))

Submission status: Runtime Error

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-

c1 = []
c2 = []
q = input().split()
for i in range(int(q[1])):
  n = input()
for j in range(n):
  m = j.split()
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])

if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

Submission status: Runtime Error

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-

c1 = []
c2 = []
q = input().split()
n = [input() for i in range(int(q[1]))]
for j in range(n):
  m = j.split()
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

Submission status: Runtime Error

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-

c1 = []
c2 = []
q = input().split()
n = [input() for i in range(int(q[1]))]
for j in range(n):
  m = j.split()
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1).intersection(c2):
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

Submission status: Runtime Error

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-

c1 = []
c2 = []
q = input().split()
n = [input() for i in range(q[1])]
for j in range(n):
  m = j.split()
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
for l in len(c2):
  if c1[l] in c2:
    print("POSSIBLE")
    break
print("INPOSSIBLE")

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys

def main():

    n, m = sys.stdin.readline().strip().split(" ")

    n = int(n)
    m = int(m)
    vis = map(lambda _: False, list(range(m+1)))

    ans = False

    for i in range(m):
        a, b = sys.stdin.readline().strip().split(" ")
        a = int(a)
        b = int(b)

        if (a == 1):
            if (vis[b] == True):
                ans = True
            else:
                vis[b] = True
        elif (b == n):
            if (vis[a] == True):
                    ans = True
            else:
                    vis[a] = True;
                
        

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys

def main():

    n, m = sys.stdin.readline().strip().split(" ")

    n = int(n)
    m = int(m)
    vis = map(lambda _: False, list(range(m+1)))

    ans = False

    for i in range(m):
        a, b = sys.stdin.readline().strip().split(" ")
        a = int(a)
        b = int(b)

        if (a == 1):
            if (vis[b] == True):
                ans = True
            else:
                vis[b] = True
        elif (b == n):
            if (vis[a] == True):
                    ans = True
            else:
                    vis[a] = True;
                
        

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
set1=set()
setn=set()
for i in [None]*M:
    ipt=[int(x) for x in input().split()]
    if 1 in ipt:
        set1 = set1.union(ipt)
    if N in ipt:
        setn = setn.union(ipt)
if set1.symmetric_difference(setn):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
des = [0]*(n+1)
a = 1

for i in range(0,m):
  b = (list(map(int,input().split()))
  if b[0] == 1:
    des[b[1]] += 1
    if des[b[1]] == 2:
      print('possible')
      a = 0
      break
    
    if b[1]  == n:
      des[b[0]] += 1
      if des[b[0]] == 2:
        print ('possible')
        a = 0
        break
if a:
  print('impossible')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
des= [0]*(n+1)
a = 1
for i in range(0, m):
    b = (list(map(int, input().split())))
    if b[0] == 1:
    	des[b[1]] += 1
    	if des[b[1]] == 2:
    		print('POSSIBLE')
    		a = 0
    		break
    if b[1] == n:
    	des[b[0]] += 1
    	if des[b[0]] == 2:
    		print('POSSIBLE')
    	        a = 0
    		break
    		
if a:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
    n, m = map(int, input().split())
    des= [0]*(n+1)
    a = 1
    for i in range(0, m):
    	b = (list(map(int, input().split())))
    	if b[0] == 1:
    		des[b[1]] += 1
    		if des[b[1]] == 2:
    			print('POSSIBLE')
    			a = 0
    			break
    	if b[1] == n:
    		des[b[0]] += 1
    		if des[b[0]] == 2:
    			print('POSSIBLE')
    			a = 0
    			break
    		
    if a:
    	print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
# coding: utf-8
     
    N, M = tuple(map(int, input().split()))
     
    graph = [ [] for i in range(N+1)]
    for i in range(M):
        a, b = tuple(map(int, input().split()))
        graph[a].append(b)
        graph[b].append(a)
     
    res = "IMPOSSIBLE"
    for i in range(2, N):
        if 1 in graph[i] and N in graph[i]:
            res = "POSSIBLE"
     
    print(res)

Submission status: Runtime Error

Solution code:
n, m = (int(i) for i in input().split())
bool_1 =[False for i in range(m)]
bool_n =[False for i in range(m)]

for i in range(m):
    a, b = (int(i)-1 for i in input().split())
    if a == 0:
        bool_1[b] = True
    if b == n-1:
        bool_n[a] = True

ans = "IMPOSSIBLE"
for i in range(len(bool_1)):
    if bool_1[i] and bool_n[i]:
        ans = "POSSIBLE"
        break

print(ans)

Submission status: Runtime Error

Solution code:
n, m = (int(i) for i in input().split())
bool_1 =[False for i in range(m)]
bool_n =[False for i in range(m)]

for i in range(m):
    a, b = (int(i) for i in input().split())
    if a == 1:
        bool_1[b] = True
    if b == n:
        bool_n[a] = True

ans = "IMPOSSIBLE"
for i in range(len(bool_1)):
    if bool_1[i] == True and bool_n[i] == True:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Runtime Error

Solution code:
n, m = (int(i) for i in input().split())
bool_1 =[False for i in range(20010)]
bool_n =[False for i in range(20010)]

for i in range(m):
    a, b = (int(i) for i in input().split())
    if a == 1:
        bool_1[b] = True
    if b == n:
        bool_n[a] = True
        
ans = "IMPOSSIBLE"
for i in range(len(bool_1)):
    if bool_1[i] == True and bool_n[i] == True:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

N2 = str(N)

d = []
n = 0
d2 =[]
d3 =[]

for i in range(M):
    a = str(input())
    d.append(a)

    a = 0

for i in range(M):
    if d[n][0] == '1':
        d2.append(d[n])

    if d[n][2] == 'N2':
        d3.append(d[n])

    n += 1

if d2 == 0 or d3 == 0:
    print('IMPOSSIBLE')
    pass

l = 0
m = 0

a_j = 0

for i in range(len(d2) - 1):
    if d2[l][2] == d3[m][0]:
        print('POSSIBLE')
        a_j = 1
    
    m += 1

    if m == len(d2) - 1:
        m = 0
        l += 1

    if l > len(d2) - 2:
        break

if a_j == 0:
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

N2 = str(N)

d = []
n = 0
d2 =[]
d3 =[]

for i in range(M):
    a = str(input())
    d.append(a)

    a = 0

for i in range(M):
    if d[n][0] == '1':
        d2.append(d[n])

    if d[n][2] == 'N2':
        d3.append(d[n])

    n += 1

if d2 == 0 or d3 == 0:
    print('IMPOSSIBLE')
    pass

l = 0
m = 0

a_j = 0

for i in range(len(d2) - 1):
    if d2[l][2] == d3[m][0]:
        print('POSSIBLE')
        a_j = 1
    
    m += 1

    if m == len(d2) - 1:
        m = 0
        l += 1

    if l > len(d2) - 1:
        break

if a_j == 0:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [0] * M
b = [0] * M

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

index = []
for i in range(M):
    if b[i] == N:
        index  = i

for j in range(M):
    if b[j] == a[index]:
        if a[j] == 1:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
        break

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [0] * M
b = [0] * M

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

index = []
for i in range(M):
    if b[i] == N:
        index  = i

for j in range(M):
    if b[j] == a[index]:
        print(a[j])
        if a[j] == 1:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
        break

Submission status: Runtime Error

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

N2 = str(N)

d = []
n = 0
d2 =[]
d3 =[]

for i in range(M):
    a = str(input())
    d.append(a)

    a = 0

for i in range(M):
    if d[n][0] == '1':
        d2.append(d[n])

    if d[n][2] == 'N2':
        d3.append(d[n])

    n += 1

if d2 == 0 or d3 == 0:
    print('IMPOSSIBLE')
    pass

l = 0
m = 0

a_j = 0

for i in range(len(d2) - 1):
    if d2[l][2] == d3[m][0]:
        print('POSSIBLE')
        a_j = 1
    
    m += 1

    if m == len(d2) - 1:
        m = 0
        l += 1

if a_j == 0:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
     if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = []
for tag in list1:
    matched_list+=filter(lambda str: str == tag, nlist)
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Runtime Error

Solution code:
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
     if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Runtime Error

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

N2 = str(N)

d = []
n = 0
d2 =[]
d3 =[]

for i in range(M):
    a = str(input())
    d.append(a)

    a = 0

for i in range(M):
    if d[n][0] == '1':
        d2.append(d[n])

    if d[n][2] == 'N2':
        d3.append(d[n])

    n += 1

l = 0
m = 0

a_j = 0

for i in range(len(d2) - 1):
    if d2[l][2] == d3[m][0]:
        print('POSSIBLE')
        a_j = 1
    
    m += 1

    if m == len(d2) - 1:
        m = 0
        l += 1

if a_j == 0:
    print('IMPOSSIBLE')

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:
        ship.append((a, b))
if len(ship) == 0:
    print("IMPOSSIBLE")
    exit()

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1
if i == len(ship):
    print("IMPOSSIBLE")


for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()
        elif ship[j][1] < ship[k][0]:
            break

print("IMPOSSIBLE")

Submission status: Runtime Error

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

N2 = str(N)

d = []
n = 0
d2 =[]
d3 =[]

for i in range(M):
    a = str(input())
    d.append(a)

    a = 0

for i in range(M):
    if d[n][0] == '1':
        d2.append(d[n])

    n += 1

n = 0

for i in range(M):
    if d[n][2] == 'N2':
        d3.append(d[n])

    n += 1

l = 0
m = 0

a_j = 0

for i in range(len(d2) - 1):
    if d2[l][2] == d3[m][0]:
        print('POSSIBLE')
        a_j = 1
    
    m += 1

    if m == len(d2) - 1:
        m = 0
        l += 1

if a_j == 0:
    print('IMPOSSIBLE')

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:
        ship.append((a, b))
if len(ship) == 0:
    print("IMPOSSIBLE")
    exit()

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1
if i == len(ship):
    print("IMPOSSIBLE")
    

for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()
        elif ship[j][1] < ship[k][0]
            break

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
use = int(input())

if use < 4:
    print(1)
elif use < 8:
    print(4)
elif use < 16:
    print(8)
elif use < 32:
    print(16)
elif use < 64:
    print(32)
elif use > 63:
    print(64)

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:
        ship.append((a, b))
if len(ship) == 0:
    print("IMPOSSIBLE")
    exit()
    
ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1

for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()
        elif ship[j][1] < ship[k][0]
            break

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
use = int(input())

if use < 4:
    print(1)
elif use < 8:
    print(4)
elif use < 16:
    print(8)
elif use < 32:
    print(16)
elif use < 64:
    print(32)
else:
    print(64)

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:
        ship.append((a, b))

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1

for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

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:
        ship.append((a, b))

ship.sort()
print(ship)
i = 0

while ship[i][0] == 1:
    i += 1

for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

N2 = str(N)

d = []
n = 0
d2 =[]
d3 =[]

for i in range(M):
    a = str(input())
    d.append(a)

    a = 0

for i in range(M):
    if d[n][0] == '1':
        d2.append(d[n])

    n += 1

n = 0

for i in range(M):
    if d[n][2] == 'N2':
        d3.append(d[n])

    n += 1

l = 0
m = 0

a_j = 0

for i in range(len(d2)):
    if d2[l][2] == d3[m][0]:
        print('POSSIBLE')
        a_j = 1
    
    m += 1

    if m == len(d2) - 1:
        m = 0
        l += 1

if a_j == 0:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
a=[],b=[],c=[]
flag=0
for i in range(M):
    x,y=map(int,input().split())
    x.append(a)
    y.append(b)
    if x==1:
        c.append(y)
for i in range(M):
    if b[i]==N:
        if a[i] in c:
            flag+=1
if flag==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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:
        ship.append((a, b))

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1

for j in range(i):
    for k in range(i, m):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

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:
        ship.append((a, b))

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1

for j in range(i):
    for k in range(i+1, m):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

ship.sort()
for s in ship:
    if s[0] != 1 and s[1] != n:
        ship.remove(s)

i = 0

while ship[i][0] == 1:
    i += 1

for j in range(i):
    for k in range(i+1, m):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

ship.sort()
for s in ship:
    if s[0] != 1 and s[1] != n:
        ship.remove(s)

i = 0

while ship[i][0]:
    i += 1

for j in range(i):
    for k in range(i+1, m):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys

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

def search(goal, path):
    n = path[len(path) - 1]
    if n == goal - 1:
        if len(path) < 4:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        sys.exit()
        
    else:
        if n < len(voyages):
            for x in voyages[n]:
                if x not in path:
                    path.append(x)
                    search(goal, path)
                    path.pop()
        else:
            print("IMPOSSIBLE")
            sys.exit()
            
search(N, [0])

Submission status: Runtime Error

Solution code:
d = {}
graph = {}

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            minn = 1e+9
            for i in graph[vertex]:
                minn = min (d[i], minn)
            d[vertex] = min(minn + 1, d[vertex])
            queue.extend(graph[vertex] - visited)
    return visited

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

for i in range(m):
    a, b = map(int, raw_input().split())
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
    d[a] = 1e+9
    d[b] = 1e+9

d[1] = 0
bfs(graph, 1)
if d[n] == 1 or d[n] == 2:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Submission status: Runtime Error

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

f = []
s = []
for i in range(M):
    a = list(map(int, input().split()))
    if a[0] == 1:
        f.append(s)
    elif a[1] == N:
        s.append(s)
a=1
for i in f:
    for j in s:
        if i[1] == j[0]:
            print("POSSIBLE")
            a=0
if a:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys

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

def search(goal, path):
    n = path[len(path) - 1]
    if n == goal - 1:
        if len(path) < 4:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        sys.exit()
        
    else:
        if n <= len(voyages):
            for x in voyages[n]:
                if x not in path:
                    path.append(x)
                    search(goal, path)
                    path.pop()
        else:
            print("IMPOSSIBLE")
            sys.exit()
            

if len(voyages) == 1:
    if not (N in voyages[0]):
        print("IMPOSSIBLE")
else:
    search(N, [0])

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
a = []
b = []
ikeru = [0]*(N+1)
for i in range(M):
    a_tmp, b_tmp = map(int, raw_input().split())
    a.append(a_tmp)
    b.append(b_tmp)

for i in range(M):
    if a[i] == 1:
        ikeru[b[i]] = 1
ikeru_2 = [0]*(N+1)
for i in range(M):
    if ikeru[a[i]] == 1:
        ikeru_2[b[i]] = 1
if ikeru_2[N] == 1 or ikeru[N] == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

f = []
s = []
for i in range(M):
    a = list(map(int, input().split()))
    if a[0] == 1:
        f.append(s)
    elif a[1] == N:
        s.append(s)
a=0
for i in f:
    for j in s:
        if i[1] == j[0]:
            print("POSSIBLE")
            a=1
if a:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
a = []
b = []
ikeru = [0]*(N+1)
for i in range(M):
    a_tmp, b_tmp = map(int, raw_input().split())
    a.append(a_tmp)
    b.append(b_tmp)

for i in range(M):
    if a[i] == 1:
        ikeru[b[i]] = 1
ikeru_2 = [0]*(N+1)
for i in range(M):
    if ikeru[a[i]] == 1:
        ikeru_2[b[i]] = 1
if ikeru_2[N] == 1 || ikeru[N] == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, raw_input().split())
a = []
b = []
ikeru = [0]*(N+1)
for i in range(M):
    a_tmp, b_tmp = map(int, raw_input().split())
    a.append(a_tmp)
    b.append(b_tmp)

for i in range(M):
    if a[i] == 1:
        ikeru[b[i]] = 1
ikeru_2 = [0]*(N+1)
for i in range(M):
    if ikeru[a[i]] == 1:
        ikeru_2[b[i]] = 1
if ikeru_2[N] == 1 || ikeru[N] == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

f = []
s = []
for i in range(M):
    a = list(map(int, input().split()))
    if a[0] == 1:
        f.append(s)
    elif a[1] == N:
        s.append(s)
a=0
for i in f:
    for j in s:
        if i[1] == j[0]:
            print("POSSIBLE")
            a=1
if a:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, raw_input().split())
a = []
b = []
ikeru = [0]*(N+1)
for i in range(M):
    a_tmp, b_tmp = map(int, raw_input().split())
    a.append(a_tmp)
    b.append(b_tmp)

for i in range(M):
    if a[i] == 1:
        ikeru[b[i]] = 1
if ikeru[N] == 1:
    print("POSSIBLE")
    sys.exit()
ikeru_2 = [0]*(N+1)
for i in range(M):
    if ikeru[a[i]] == 1:
        ikeru_2[b[i]] = 1
if ikeru_2[N] == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import sys

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

def search(goal, path):
    n = path[len(path) - 1]
    if n == goal - 1:
        if len(path) < 4:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        sys.exit()
        
    else:
        for x in voyages[n]:
            if x not in path:
                path.append(x)
                search(goal, path)
                path.pop()

if len(voyages) == 1:
    if not (N in voyages[0]):
        print("IMPOSSIBLE")
else:
    search(N, [0])

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(M))

    if M == 1:
        print('IMPOSSIBLE')
        return

    for a, b in A:
        if a == 1:
            relay1 = b
        elif b == N:
            relay2 = a

    if relay1 == relay2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

main()

Submission status: Runtime Error

Solution code:
N, M = int(input().split())
 
f = []
s = []
for i in range(M):
    a = list(map(int, input().split()
    if a[0] == 1:
        f.append(s)
    elif a[1] == N:
        s.append(s)
a = 0
for i in f:
    for j in s:
        if i[1] == j[0]:
            print("POSSIBLE")
            a = 1
if a :
    print("IMPOSSIBLE")

Submission status: Runtime Error

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

f = []
s
for i in range(M):
    a = list(map(int, input().split()
    if a[0] == 1:
        f.append(s)
    elif a[1] == N:
        s.append(s)
a = 0
for i in f:
    for j in s:
        if i[1] == j[0]:
            print("POSSIBLE")
            a = 1
if a :
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
    import sys
    N, M = map(int, input().split())
    routes = []
    for i in range(M):
        a, b = map(int, input().split())
        routes.append([a, b])
    m = []
    for r in routes:
        if r[0] == 1:
            m.append(r[1])
    for r in routes:
        if r[0] in m:
            if r[1] == N:
                print('POSSIBLE')
                sys.exit()
    print('IMPOSSIBLE')

Submission status: Runtime Error

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

for i in range(m):
    if ship[i][0] == 1:
        for j in range(i+1, m):
            if ship[i][1] == ship[j][0] and ship[j][1] == n or ship[i][1] == ship[j][1] and ship[j][0] == n:
                print("POSSIBLE")
                exit()
    elif ship[i][1] == 1:
        for j in range(i+1, m):
            if ship[i][0] == ship[j][0] and ship[j][1] == n or ship[i][0] == ship[j][1] and ship[j][0] == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")