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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
z = []
p = 0
for i in range(m):
    x,y = map(int,input().split())
    if x == 1:
        z.append(y)
    elif y == n:
        a.append(x)
        p += 1
    else:
        pass
flg = False
for i in range(p):
    if a[i] in z:
        flg = True
        break
if flg:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

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

travellist = sorted(travellist)


To_list = []
for i in range(M):

    oneroot = travellist[i]
    From = oneroot[0]
    To   = oneroot[1]

    if From == 1:
        To_list.append(To)

    if To == N and From in To_list:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

list_A = []
list_B = []
for _ in range(M):
    a, b = map(int, input().split())
    list_A.append(a)
    list_B.append(b)


visitlist = []  
for i in range(M):
    if list_B[i] == N:
        visitlist.append(list_A[i])

for j in range(M):
    if list_A[j] == 1 and list_B[j] in visitlist:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

G1 = []
GN =[]

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

res = False

for obj in G1:
    if obj in GN:
        res = True
        break


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

Submission status: Time Limit Exceeded

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

G = {i:[] for i in range(1, N + 1)}

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

res = False

for obj in G[1]:
    if obj in G[N]:
        res = True
        break


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

Submission status: Time Limit Exceeded

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

edges = {i : [] for i in range(1, N+1)}
for _ in range(M):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)

def dfs(n, count):
  # 定期便2つでは行けない
  if count == 3:
    return False
  if n == N:
    return True
  
  for edge in edges[n]:
    if dfs(edge, count + 1):
      return True
  
  return False

print("POSSIBLE" if dfs(1, 0) else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(m)]
l.sort()
a,b = [list(i) for i in zip(*l)]
z = []
for i in range(m):
    if a[i] == 1:
        x = b[i]
        for j in range(i+1,m):
            if x == a[j]:
                if n == b[j]:
                    print('POSSIBLE')
                    exit(0)
            elif x >= a[j]:
                pass
            else:
                break
    else:
        break
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
s=[tuple(map(int,input().split())) for _ in range(m)]
d=defaultdict(int)
for x in s:
  d[x[0]]|=(1<<x[1])
  d[x[1]]|=(1<<x[0])
if d[1]&d[n]>0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l1 = []
ln = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l1.append(b)
    elif b == 1:
        l1.append(a)
    elif a == n:
        ln.append(b)
    elif b == n:
        ln.append(a)
l1.sort()
ln.sort()
ans = False
for i in l1:
    for j in ln:
        if i == j:
            ans = True
            break
        if i < j:
            break
    if ans:
        break
if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ans = False
for i in l1:
    if i in ln:
        ans = True
        break
if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
goal = n
tmp,ans = [],[]
for i in range(m):
	if a[i][1] == goal:
		tmp.append(a[i][0])
#print(tmp)
for j in range(m):
		if a[j][0] == start:
			if a[j][1] in tmp:
				print('POSSIBLE')
				sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
goal = n
tmp,ans = [],[]
for i in range(m):
	if a[i][1] == goal:
		tmp.append(a[i][0])
#print(tmp)
for j in range(m):
		if a[j][0] == start:
			if a[j][1] in tmp:
				print('POSSIBLE')
				sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
def bfs():
    queue = Queue()
    queue.put((1, 0))
    visited = [False]*(n+1)
    while not queue.empty():
        u, step = queue.get()
        if u == n and step == 2:
            print ("POSSIBLE")
            return
        for a in adj[u]:
            if step + 1 <= 2:
                queue.put((a, step+1))
    print ("IMPOSSIBLE")
    return
bfs()

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
tmp,ans = [],[]
for i in range(m):
	if a[i][0] == start:
		tmp.append(a[i][1])
for j in range(m):
	for k in range(len(tmp)):
		if a[j][0] == tmp[k] :
			if a[j][1] == n:
				print('POSSIBLE')
				sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
x=[]
y=[]
for i in lst:
  if i[0]==1:
    x+=[i[1]]
for i in lst:
  if i[1]==n:
    y+=[i[0]]
ans='IMPOSSIBLE'
for i in x:
  if i in y:
    ans='POSSIBLE'
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
a.sort()
#print(a)
d=[]
for i in range(m):
    if a[i][0]==1:
        d.append(a[i][1])
    else:
        break
e=[]
for i in range(m):
    if a[i][1]==n:
        e.append(a[i][0])
if len(d)>=len(e):
    for i in range(len(e)):
        if e[i] in d:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')
else:
    for i in range(len(d)):
        if d[i] in e:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')
#print([d[0],n])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
a.sort()
#print(a)
d=[]
for i in range(m):
    if a[i][0]==1:
        d.append(a[i][1])
    else:
        break
e=[]
for i in range(m):
    if a[i][1]==n:
        e.append(a[i])
for i in range(len(d)):
    if [d[i],n] in e:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')
#print([d[0],n])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
a.sort()
#print(a)
d=[]
for i in range(m):
    if a[i][0]==1:
        d.append(a[i][1])
    else:
        break
for i in range(len(d)):
    if [d[i],n] in a:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')
#print([d[0],n])

Submission status: Time Limit Exceeded

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

data = list()
list_of_one = list()
for i in range(M):
    tup = tuple(map(int, input().split()))
    if tup[0] == 1:
        list_of_one.append(tup[1])
    else:
        data.append(tup)

for entry in data:
    if entry[0] in list_of_one and entry[1] == N:
        found = True

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

Submission status: Time Limit Exceeded

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

data = list()
for i in range(M):
    tup = tuple(map(int, input().split()))
    data.append(tup)

for entry in data:
    if entry[0] == 1:
        for sub in data:
            if sub[0] == entry[1]:
                if sub[1] == N:
                    found = True

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
S = [list(map(int,input().split())) for m in range(M)]
T = [s for s in S if 1 in s or N in s]
ans = "IMPOSSIBLE"

for n in range(1+N):
  if [1,n] in T and [n,N] in T:
    ans = "POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
S = [list(map(int,input().split())) for m in range(M)]
ans = "IMPOSSIBLE"

for n in range(1+N):
  if [1,n] in S and [n,N] in S:
    ans = "POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
for num in sorted(teiki_1):
    if num in sorted(teiki_N):
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
for num in teiki_1:
    if num in teiki_N:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
left = deque([])
right = deque([])
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
left = deque([])
right = deque([])
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

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

for x in li_s:
    if x in li_g:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

for x in li_s:
    if x in li_g:
        print("POSSIBLE")
        break
    if x == li_s[-1]:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,m = readInts()
ab = [readInts() for i in range(m)]
go1 = []
for i in range(m):
	if ab[i][0]==1:
		go1.append(ab[i][1])
for i in range(m):
	if ab[i][0] in go1 and ab[i][1]==n:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

dist = [float('inf')] * n
def dfs(s, p, depth):
    dist[s] = min(dist[s], depth)
    for to in g[s]:
        if to==p: continue
        if dist[to] < dist[s]+1: continue
        dfs(to, s, depth+1)

dfs(0, -1, 0)

if dist[n-1] <= 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in l:
  if i[0] == n:
    c.append(i[1])
    l.remove(i)
  elif i[1] == n:
    c.append(i[0])
    l.remove(i)
  elif 1 in i:
    continue
  else:
    l.remove(i)
    
for i in range(len(l)):
  if l[i][0] == 1:
    if l[i][1] in c:
      print('POSSIBLE')
      exit()
  if l[i][1] == 1:
    if l[i][0] in c:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in range(m):
  if l[i][0] == n:
    c.append(l[i][1])
  elif l[i][1] == n:
    c.append(l[i][0])

for i in range(m):
  if l[i][0] == 1:
    if l[i][1] in c:
      print('POSSIBLE')
      exit()
  if l[i][1] == 1:
    if l[i][0] in c:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in range(m):
  if l[i][0] == n:
    c.append(l[i][1])
  elif l[i][1] == n:
    c.append(l[i][0])

for i in l:
  for j in c:
    if i == [1, j] or i == [j, 1]:
      d = 1
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in range(m):
  if l[i][0] == n:
    c.append(l[i][1])
  elif l[i][1] == n:
    c.append(l[i][0])
d = 0
for i in l:
  for j in c:
    if i == [1, j] or i == [j, 1]:
      d = 1
print('POSSIBLE' if d == 1 else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"

start_lst = []
goal_lst = []
for a in a_lst:
  if a[0] == 1:
    start_lst.append(a[1])
  if a[1] == n:
    goal_lst.append(a[0])
    
for s in start_lst:
  if s in goal_lst:
    ans = "POSSIBLE"
    
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ipponme=[]

for i in lst:
    if i[0]==1:
        ipponme.append(i[1])

for i in ipponme:
    for j in lst:
        if j[0]==i and j[1]==n:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]
ln1 = []
ln2 = []
for i in p:
    if i[0] == 1:
        ln1.append(i[1])
for j in p:
    if j[1] == n:
        ln2.append(j[0])

for k in ln1:
    if k in ln2:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

hune = [[] for _ in range(n + 1)]

AB.sort(key=lambda x: x[0])
totyu = []
for a, b in AB:
    if a == 1:
        totyu.append(b)
    if b == n and a in totyu:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
from collections import deque
q = deque([])
q.append(1)
reach = [0]*(n+1)
reach[0] = -1
while q:
    x = q.popleft()
    for v in V[x]:
        if reach[v] == 0:
            q.append(v)
            reach[v] = reach[x]+1
    if max(reach) >= 3:
        break
if reach[-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for j in A[0]:
    if j in A[-1]:
        print("POSSIBLE")
        break
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        if a == n:
            ln.append(b)
        else:
            ln.append(a)

for i in la:
    if i in ln:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        if a == n:
            ln.append(b)
        else:
            ln.append(a)

for i in ln:
    if i in la:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def LIST():
    return list(map(int, input().split()))

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

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        ln.append(a*b/n)

for i in la:
    if i in ln:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = []
for i in range(m):
    if ls[i][0] == 1:
        di.append(ls[i][1])
for j in range(m):
    if ls[j][0] in di and ls[j][1] == n:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for num in one_next:
    if num in n_next:
        print("POSSIBLE")
        break
else:
     print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m = map(int, input().split())
from_start = np.array([])
to_end = np.array([])

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start = np.append(from_start, temp[1])
  elif temp[1]==n:
    to_end = np.append(to_end, temp[0])

  if from_start in to_end:
    print('POSSIBLE')
    break
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start.append(temp[1])
  elif temp[1]==n:
    to_end.append(temp[0])
else:
  for i in from_start:
    if i in to_end:
      print('POSSIBLE')
      break
  else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        #0-indexedでなくてもよいことに注意
        #u = from, v = to, d = cost
        #directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        #0-indexedでなくてもよいことに注意
        #:param s: 始点
        #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


N, M = map(int, input().split())
islands = Dijkstra()
for _ in range(M):
    a, b = map(int, input().split())
    islands.add(a, b, 1)

dis = islands.Dijkstra_search(1)[0][N]

if dis > 2:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
P, M = ("POSSIBLE", "IMPOSSIBLE")
dic = {}
for _ in range(m):
    a, b = map(int, input().split())
    if dic.get(a) is None: dic[a] = [b]
    else: dic[a] = dic[a] + [b]
    if dic.get(b) is None: dic[b] = [a]
    else: dic[b] = dic[b] + [a]
if dic.get(n) is None:
    print(M)
    exit()
arr = dic[n]
for i in arr:
    if 1 in dic[i]:
        print(P)
        exit()
print(M)

Submission status: Time Limit Exceeded

Solution code:
def answer(destination, services):
    P, M = ("POSSIBLE", "IMPOSSIBLE")
    dic = {}
    for a, b in services:
        if dic.get(a) is None:
            dic[a] = [b]
        else:
            dic[a] = dic[a] + [b]
        if dic.get(b) is None:
            dic[b] = [a]
        else:
            dic[b] = dic[b] + [a]
    if dic.get(destination) is None: return M
    arr = dic[destination]
    for i in arr:
        if 1 in dic[i]:
            return P
    return M

n, m = map(int, input().split())
services = []
for _ in range(m):
    a, b = map(int, input().split())
    services.append((a, b))
print(answer(n, services))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, m = input_list()
    starts = []
    ends = []
    for _ in range(m):
        a, b = input_list()
        if a == 1:
            starts.append(b)
        elif b == n:
            ends.append(a)
    s = list(sorted(starts))
    e = list(sorted(ends))
    for a in s:
        if a in e:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, m = input_list()
    starts = []
    ends = []
    for _ in range(m):
        a, b = input_list()
        if a == 1:
            starts.append((a, b))
        elif b == n:
            ends.append(a)
    for a, b in starts:
        if b in ends:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

fukasa = [10**18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
listmada = [0]
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in listmada[:]:
		settansaku.add(i)
		listmada.remove(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					listmada.append(k)
					setmada.add(k)
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

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

q = deque([(1, 0)])
while q:
    p, c = q.popleft()
    if c > 2:
        continue
    if p == N:
        print("POSSIBLE")
        sys.exit()
    for next_p in paths[p]:
        q.append((next_p, c+1))

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
n, m = map(int, input().split())
L = [[0]*n for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    L[a-1][b-1] = 1
    L[b-1][a-1] = 1

L = wf(L)

if L[0][n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)


for i in set(lis[-1]):
  if i in set(lis[0]):
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

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


for i in lis[-1]:
  if i in set(lis[0]):
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

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

lis[0].reverse()

for i in lis[-1]:
  if i in set(lis[0]):
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')