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: Wrong Answer

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])
print(m)
for r in routes:
    if r[0] in m:
        if r[1] == N:
            print('Possible')
            sys.exit()
print('Impossible')

Submission status: Wrong Answer

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

g = [ [] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

x=0
y=0

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

if(x==y):
	ans="POSSIBLE"
else:
	ans="IMPOSSIBLE"

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ship = []
for i in range(m):
    ship.append(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")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = 1
count = 0
msg = "IMPOSSIBLE"
for i in range(m):
 a,b = map(int,input().split())
 if a == l:
  l = b
 count += 1
 if count > 2:
  break
 if b == n:
  msg = "POSSIBLE"
  break
print(msg)

Submission status: Wrong Answer

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

for i in range(M):
	if c[i][0] == 1:
		for j in range(M):
			if c[j][0] == c[i][0]:
				if c[j][1] == N:
					print('POSSIBLE')
					exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

flag = 0
for n in range(2,N+1):
    print(n)
    if [1,n] in ships and [n,N] in ships:
        print("POSSIBLE")
        flag=1
        break

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

Submission status: Time Limit Exceeded

Solution code:
# C - Cat Snuke and a Voyage
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab_1 = [ab[i][1] for i in range(m) if ab[i][0] == 1]
    ab_m = [ab[i][0] for i in range(m) if ab[i][1] == n]

    for i in ab_1:
            for j in ab_m:
                if i == j:
                    print('POSSIBLE')
                    exit()
    else:
        print('IMPOSSIBLE')

if __name__ ==  "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# C - Cat Snuke and a Voyage
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]

    for a, b in ab:
        if a == 1:
            for a1, b1 in ab:
                if b == a1 and b1 == n:
                    print('POSSIBLE')
                    exit()
    else:
        print('IMPOSSIBLE')

if __name__ ==  "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = []
b = []
for i in range(M):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

c = []
clear = 0

for i in range(M):
    if b[i] == N:
        c.append(a[i])

for i in range(M):
    if a[i] == 1 and b[i] in c:
        clear = 1
        break

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

Submission status: Time Limit Exceeded

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

pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

for i in set(pot_starts):
    if i in pot_ends:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

potential_ends =   [i[0] for i in a if i[1] == n]
potential_starts = [i[1] for i in a if i[0] == 1]

for p in potential_starts:
    if p in potential_ends:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

potentials = [i for i in a if i[1] == n]

for p in potentials:
    if [1, p[0]] in a:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

def main():
    n, m = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(m)])
    ans = "IMPOSSIBLE"
    for i in range(m):
        if ab[i][0] == 1:
            if [ab[i][1], n] in ab[i + 1:]:
                ans = "POSSIBLE"
        else:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    ans = "IMPOSSIBLE"
    for i in range(m):
        if ab[i][0] == 1:
            if [ab[i][1], n] in ab:
                ans = "POSSIBLE"
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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


for x in a1:
  if x in bn:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

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


for x in a1:

    if x in bn:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

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

x = len(ab) # length ab
for i in range(x):
  for j in range(x):
    if ab[i][0] == ab[j][1]:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

if len(x)==0 or len(y)==0:
  print("IMPOSSIBLE")
  exit()

ans="IMPOSSIBLE"

for i in range(len(y)):
  if y[i] in x:
    ans="POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

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

ans="IMPOSSIBLE"

for i in range(len(y)):
  if y[i] in x:
    ans="POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

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

ans="IMPOSSIBLE"

for i in range(len(x)):
  if x[i] in y:
    ans="POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
L.sort(key=lambda x: x[0])
funes1 = []
for a,b in L:
    if a == 1:
        funes1.append(b)
    else:
        if a in funes1:
            if b == N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
L.sort(key=lambda x: x[0])
funes1 = []
for a,b in L:
    if a != 1:
        break
    funes1.append(b)
funes1.sort()
for f in funes1:
    for a,b in L:
        if a > f:
            break
        if f == a:
            if b == N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
data=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    if b not in data:
      data.append(b)
    else:
      print('POSSIBLE')
      exit()
  elif b==n:
    if a not in data:
      data.append(a)
    else:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
data=[]
res=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    data.append(b)
  elif b==n:
    res.append(a)
for i in data:
  if i in res:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

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

    c = [[INF]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b = i_map()
        c[a-1][b-1] = 1
        c[b-1][a-1] = 1

    for i,k in enumerate(c[0]):
        if k == 1:
            if c[i][-1] == 1:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE")


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

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

    c = [[INF]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b = i_map()
        c[a-1][b-1] = 1
        c[b-1][a-1] = 1

    for i,k in enumerate(c[0]):
        pass
        if k == 1:
            if c[i][-1] == 1:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE")





if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

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

    c = [[INF]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b = i_map()
        c[a-1][b-1] = 1
        c[b-1][a-1] = 1


    for k in range(n): # 経由
        for i in range(n): # 始点
            for j in range(n): # 終点
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])
    if c[0][-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")





if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

check = 0


for i in range(m):
    if a[i] == 1:
        check = b[i]
        for j in range(m):
            if a[j] == check and b[j] == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():
    N, M = map(int, input().split())

    l = [[0] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        l[a-1][b-1] = 1
        l[b-1][a-1] = 1

    csr = csr_matrix(l)

    res = dijkstra(csr)
    if res[0][N-1] == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
nekotyann=[]
wanntyann=[]
ans="IMPOSSIBLE"
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        nekotyann.append(b)
    if b==N:
        wanntyann.append(a)
for i in range(len(wanntyann)):
    if wanntyann[i] in nekotyann:
        ans="POSSIBLE"
        break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

n,m=map(int,input().split())
a,b,c=[],[],[]
for i in range(m):
    A=list(map(int,input().split()))
    a.append(A)
for i in range(m):
    if a[i][1]==n:
        b.append(a[i][0])
    elif a[i][0]==1:
        c.append(a[i][1])
if len(b)>0:
    b=list(set(b))
    c=list(set(c))
    for i in b:
        for j in c:
            if i==j:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    queue = collections.deque([1])
    explored = set()
    cnt = 1
    level = 0

    while len(queue)!=0 and not (level==2 and cnt==0):
        if cnt==0:
            level+=1
            cnt+=len(queue)
        ex = queue.popleft()
        explored.add(ex)
        for i in route[ex]:
            if i not in queue and i not in explored:
                queue.append(i)
        cnt -= 1
    
    ans = n in explored
    print("POSSIBLE" if ans else "IMPOSSIBLE")
        

main()

Submission status: Time Limit Exceeded

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

t = []

for _ in range(m):
    a, b = inintm()
    if a == 1:
        if b in t:
            print("POSSIBLE")
            exit()
        t.append(b)
    elif b == n:
        if a in t:
            print("POSSIBLE")
            exit()
        t.append(a)

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

ship = []

t = []

for _ in range(m):
    a, b = inintm()
    ship.append([a, b])
    if a == 1:
        t.append(b)

for s in ship:
    if s[0] in t and s[1] == n:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import collections
N, M = map(int, input().split())
graph = collections.defaultdict(lambda:set())
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].add(b-1)
    graph[b-1].add(a-1)

def bfs(v, goal, graph, seen, next_v, rank):
    for x in graph[v]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.add(x)
    return False


next_v = [0]
rank = [0]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(next_v[0], N-1, graph, seen, next_v, rank):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
    rank.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, goal, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        if x == goal:
            return True
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.add(x)
    return False


next_v = [0]
rank = [0]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(next_v[0], N-1, graph, seen, next_v, rank):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
    rank.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.add(x)


next_v = [0]
rank = [0]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 3:
        ans = "IMPOSSIBLE"
        break
    if next_v[0] == N-1:
        ans = "POSSIBLE"
        break
    bfs(next_v[0], graph, seen, next_v, rank)
    next_v.pop(0)
    rank.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.append(x)


next_v = [0]
rank = [0]
seen = [0]
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 3:
        ans = "IMPOSSIBLE"
        break
    if next_v[0] == N-1:
        ans = "POSSIBLE"
        break
    bfs(next_v[0], graph, seen, next_v, rank)
    next_v.pop(0)
    rank.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        next_v.append(x)
        rank.append(rank[0]+1)

next_v = [0]
rank = [0]
seen = [0]
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 3:
        ans = "IMPOSSIBLE"
        break
    if next_v[0] == N-1:
        ans = "POSSIBLE"
        break
    bfs(next_v[0], graph, seen, next_v, rank)
    next_v.pop(0)
    rank.pop(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

# input
n, m = map(int, input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())

# calc
middle = []
ok = False
for i in range(m):
    if a[i] == 1:
        middle.append(b[i])
for i in range(len(middle)):
    for j in range(m):
        if a[j] == middle[i] and b[j] == n:
            ok = True
if ok: 
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
for _ in range(m):
    c=list(map(int,input().split()))
    if c[0]==1:
        a.append(c[1])
    if c[1]==n:
        b.append(c[0])
a.sort()
b.sort()
#print(a)
#print(b)
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]==b[j]:
            print("POSSIBLE")
            exit()
        if a[i]<b[j]:
            continue
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = list(map(int,input().split()))
    G = [[] for k in range(N)]
    for i in range(M):
        A, B = list(map(int,input().split()))
        G[A-1].append(B-1)
        G[B-1].append(A-1)
    for e in G[0]:
        if e in G[N-1]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]
dist = [float('inf')]*N

def dfs(u, pre, cnt):
  dist[u] = cnt
  for v in graph[u]:
    if v != pre and cnt+1 < dist[v]:
      dfs(v, u, cnt+1)

    
dfs(0, -1, 0)
if 0 < dist[N-1] <= 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'
for s1 in ship[ship.T[0] == 1]:
    for s2 in ship[ship.T[0] == s1[1]]:
        if s2[1] == N:
            ans = 'POSSIBLE'
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
B=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    A.append(b)
  if b==n:
    B.append(a)
for i in A:
  if i in B:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    mat = dijkstra(csr_matrix((np.ones(M), (a, b)), shape=(N+1, N+1), dtype=np.int32), indices=1, directed=False, limit=2)
    return YES if mat[N] <= 2 else NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

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

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


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    mat = dijkstra(csr_matrix((np.ones(M), (a, b)), shape=(N+1, N+1), dtype=np.int32), indices=1, directed=False)
    return YES if mat[N] <= 2 else NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_to = []
a_from = []
for i in range(m):
    a,b = map(int,input().split())
    if a==1:
        a_to.append(b)
    if b==1:
        a_to.append(a)
    if a==n:
        a_from.append(b)
    if b==n:
        a_from.append(a)
isOK = False
for j in range(len(a_to)):
    if a_to[j] in a_from:
        isOK = True
        break
#print(a_to)
#print(a_from)
if isOK:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
ab = []
num = 0
for i in range(m):
    a,b = map(int, input().split())
    if a == 1 or b == n:
        num += 1
        ab.append((a,b))
ab.sort()
x = 'IMPOSSIBLE'
for h in range(num):
    if (ab[h][1],n) in ab:
        x = 'POSSIBLE'
        break
print(x)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
ab = []
num = 0
for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        num += 1
    ab.append((a,b))
ab.sort()
x = 'IMPOSSIBLE'
for h in range(num):
    if (ab[h][1],n) in ab:
        x = 'POSSIBLE'
        break
print(x)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=input().split()
    if a=='1':
        A.append([int(a),int(b)])
    if b==str(n):
        B.append([int(a),int(b)])
for j in range(len(A)):
    for k in range(len(B)):
        if A[j][1] ==B[k][0]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(m):
    a,b=input().split()
    ab.append([int(a),int(b)])    
c = []
ab=list(map(list, set(map(tuple, ab))))
for j in range(len(ab)):
    if ab[j][0]==1:
        c.append(ab[j][1])
for p in range(len(ab)):
    if ab[p][1] == n and ab[p][0] in c:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
A=[]
B=[]
for i in range(m):
    a,b=input().split()
    A.append(int(a))
    B.append(int(b))
    ab.append([int(a),int(b)])
if 1 not in A or n not in B:
    print('IMPOSSIBLE')
    exit()
c = []
for j in range(len(ab)):
    if ab[j][0]==1:
        c.append(ab[j][1])
for p in range(len(ab)):
    if ab[p][1] == n and ab[p][0] in c:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(m):
    a,b=input().split()
    ab.append([int(a),int(b)])
for j in range(len(ab)):
    if ab[j][0]==1:
        for p in range(len(ab)):
            if ab[p][1] ==n and ab[j][1] == ab[p][0]:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

for i in range(M):
    if L[i][0]==1 and L[i][1]==N:
        print("POSSIBLE")
        exit()
    elif L[i][0]==1 and [L[i][1],N] in L:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in range(M):
    if L[i][0]==1 and L[i][1]==N:
        print("POSSIBLE")
        exit()
    elif L[i][0]==1:
        mylist.append(L[i])

for j in range(len(mylist)):
    if [mylist[j][1],N] in L:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")