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:
target, m = map(int, input().split())

ship_count = 1
next_ships = []
next_start = []
for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    next_start.append(b)
  else:
    if b == target:
      next_ships.append([a, b])

if len(next_start) == 0:
  print('IMPOSSIBLE')
  exit(0)

for i in next_ships:
  a, b = i[0], i[1]
  if a in next_start:
    print('POSSIBLE')
    exit(0)

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ship_count = 1
next_ships = []
next_start = []
for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    next_start.append(b)
  else:
    next_ships.append([a, b])

if len(next_start) == 0:
  print('IMPOSSIBLE')
  exit(0)

for i in next_ships:
  a, b = i[0], i[1]
  if a in next_start and b == target:
    print('POSSIBLE')
    exit(0)

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
s = []
g = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 and b == N:
        print("POSSIBLE")
        sys.exit()
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)

for i in s:
    if i in g:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
NN = [[0] * N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    NN[a-1][b-1] = 1
    NN[b-1][a-1] = 1
    if a == 1 and b == N:
        print("POSSIBLE")
        sys.exit()

for i in range(N):
    if NN[N-1][i] == 1 and NN[i][0] == 1:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import dijkstra

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

d = dijkstra(NN, directed = False, indices = 0)
    
if d[N-1] >= 3:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]
ship = sorted(ship, key=lambda x: x[0])

if M == 1:
    print("IMPOSSIBLE")
    exit()

one = []
for i in range(N):
    if ship[0][0] == 1:
        one.append(ship[0])
        ship.pop(0)
    elif ship[0][1] != N:
        ship.pop(0)

end = []
for i in range(len(ship)):
    end.append(ship[i][0])

for i in range(len(one)):
    if one[i][1] in end:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]
ship = sorted(ship, key=lambda x: x[0])

if M == 1:
    print("IMPOSSIBLE")
    exit()

one = []
for i in range(N):
    if ship[0][0] == 1:
        one.append(ship[0])
        ship.pop(0)
    elif ship[0][1] != N:
        ship.pop(0)

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

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]
ship = sorted(ship, key=lambda x: x[0])

if M == 1:
    print("IMPOSSIBLE")
    exit()

one = []
for i in range(N):
    if ship[0][0] == 1:
        one.append(ship[0])
        ship.pop(0)
    elif ship[0][1] != N:
        ship.pop(0)

i = 0
while ship:
    if ship[0][0] == one[i][1]:
        if ship[0][1] == N:
            print("POSSIBLE")
            exit()

    i += 1
    if i == len(one):
        i = 0
        ship.pop(0)

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

first = []
second = []
for i in range(m):
    a = list(map(int, input().split()))
    if a[0] == 1:
        first.append(a[1])
    if a[1] == n:
        second.append(a[0])


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

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

for i in range(m):
    if ship_list[i][0] == 1:
        first.append(ship_list[i][1])
    if ship_list[i][1] == n:
        second.append(ship_list[i][0])

for i in first:
    if i in second:
        print('POSSIBLE')
        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)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    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)]

first = []

for ab in AB:
    if ab[0] == 1:
        first.append(ab[1])

for ab in AB:
    if ab[0] in first and ab[1] == N:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

boat1 = [boatList[i] for i in range(m) if boatList[i][0] == 1]
boat1Len = len(boat1)

boat2 = [boatList[i] for i in range(m) if boatList[i][1] == n]
boat2Len = len(boat2)

del boatList

for i in range(boat2Len):
    ans = [
        True for j in range(boat1Len)
        if boat1[j][1] == boat2[i][0]
    ]

    if True in ans:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

boat1 = [i for i in range(m) if boatList[i][0] == 1]
boat1Len = len(boat1)

boat2 = [i for i in range(m) if boatList[i][1] == n]
boat2Len = len(boat2)

for i in range(boat2Len):
    ans = [
        True for j in range(boat1Len)
        if boatList[boat1[j]][1] == boatList[boat2[i]][0]
    ]

    if True in ans:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

A=[10**10]*M
B=[10**9]*M

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

A=[10**10]*M
B=[10**9]*M

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

A=[10**10]*M
B=[10**10]*M

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
root1 = []
root2 = []
for i in range(M):
    ai,bi = map(int,input().split())
    if ai==1:
        tmp = [ai,bi]
        root1.append(tmp)
    else:
        tmp = [ai,bi]
        root2.append(tmp)
for i in range(len(root1)):
    for j in range(len(root2)):
        if root1[i][1]==root2[j][0]:
            if root2[j][1]==N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m, *ab = [int(x) for x in open(0).read().split()]

from_1, to_n = [], []
for a, b in zip(*[iter(ab)] * 2):
    if a == 1: from_1.append(b)
    elif b == n: to_n.append(a)
for b in from_1:
    if b in to_n: print('POSSIBLE'); exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
l = deque(sys.stdin.readlines())
n, m = (int(x) for x in l[0].split())
l.popleft()
ab = deque()
for i in range(m):
  a, b = tuple(int(x) for x in l[i].split())
  if a == 1 or b == n: ab.append((a, b)) 
  
for i in ab:
  if i[0] == 1:
      if (i[1], n) in ab: print('POSSIBLE'); exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

ab = [may for may in ab if may[0] == 1 or may[1] == n]
ab.sort()
ab_end_n = [may for may in ab if may[1] == n]

for m in ab:
    if m[0] == 1: 
        for i in ab_end_n:
            if m[1] == i[0]: print('POSSIBLE'); exit()
        continue
    else:
        break
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

ab = [may for may in ab if may[0] == 1 or may[1] == n]
ab.sort()
ab_end_n = [may for may in ab if may[1] == n]

for m in ab:
    if m[0] == 1: 
        if (m[1], n) in ab_end_n: print('POSSIBLE'); exit()
        else:
            continue
    else:
        break
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(m)])
ans=0
a=0
for i in range(m):
    if l[i][0]!=1:
        a=i
        break
for i in range(a):
    for j in range(a,m):
        if set(l[i])^set(l[j])=={1,n}:
            ans=1
            break
print("POSSIBLE" if ans==1 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in range(m)])
ans=0
for i in range(m):
    if l[i][0]!=1:break
    else:
        for j in range(i+1,m):
            if set(l[i])^set(l[j])=={1,n}:
                ans=1
                break
print("POSSIBLE" if ans==1 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

n, m = [int(x) for x in input().split()]
ab = [tuple(int(x) for x in input().split()) for _ in range(m)]

for i in range(2, n):
    if (1, i) in ab and (i, n) in ab: print('POSSIBLE'); exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

via = []
for i, v in enumerate(sorted(boat)):
    if v[0] == 1:
        via.append(v[1])
    else:
        break

flag = False
for v in via:
    if [v, N] in boat:
        flag = True
        break

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

Submission status: Time Limit Exceeded

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

for ship1,ship2 in list(itertools.combinations(AB,2)):
  now=ship1[0]
  if now==1:
    now=ship1[1]
    if now==ship2[0] and ship2[1]==n:
      print('POSSIBLE')
      exit()
  now=ship2[0]
  if now==1:
    now=ship2[1]
    if now==ship1[0] and ship1[1]==n:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
import collections
table=collections.defaultdict(list)
for i in range(M):
  a,b=map(int,input().split())
  table[a].append(b)
  table[b].append(a)
for x in table[1]:
  if x in table[N]:
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
from collections import defaultdict 
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append(b)
    d[b].append(a)
q=[0]
dist=[0]*n 
vis=[0]*n 
vis[0]=1 
while q:
    t=q.pop(0)
    for i in d[t]:
        if not vis[i]:
            vis[i]=1 
            dist[i]=dist[t]+1 
            q.append(i)
print('POSSIBLE' if dist[n-1]==2 else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
first=[]
second=[]
for m in range(M):
    a,b=map(int,input().split())
    if a==1:
        first.append(b)
    elif b==N:
        second.append(a)
count=0
for n in first:
    if n in second:
        print('POSSIBLE')
        count=1
        break
if count==0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

g=csr_matrix((w,(ro,co)),shape=(n,n))
d=dijkstra(g,directed=False,indices=0)
if d[-1]==2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'

for i in range(2, n):
  if (1, i) in cand_path and (i, n) in cand_path:
    ans = 'POSSIBLE'
    break
  
print(ans)

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'

for i in range(2, n):
  path = [1, i, n]
  if len([True for x in zip(path, path[1:]) if x in cand_path])==2:
    ans = 'POSSIBLE'
    break
    
print(ans)

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'

for i in range(2, n):
  path = [1, n]
  path.insert(1, i)
  if len([True for x in zip(path, path[1:]) if x in cand_path])==2:
    ans = 'POSSIBLE'
    break
    
print(ans)

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'

for i in range(2, n):
  path = [1, n]
  path.insert(1, i)
  if len([True for x in zip(path, path[1:]) if x in cand_path])==2:
    ans = 'POSSIBLE'
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
island, ship = map(int, input().split())
startTo, fromGoal = [], []
for i in range(ship):
  a, b = map(int, input().split())
  if a == 1:
    startTo.append(b)
  elif b == 1:
    startTo.append(a)
  elif a == island:
    fromGoal.append(b)
  elif b == island:
    fromGoal.append(a)
check = False
if len(startTo) < len(fromGoal):
  for i in range(len(startTo)):
    check = startTo[i] in fromGoal
    if check:
      break
else:
  for i in range(len(fromGoal)):
    check = fromGoal[i] in startTo
    if check:
      break
if check:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
start = set()
goal = set()
for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        start.add(b)
    elif  b == n:
        goal.add(a)

for i in start:
    for j in goal:
        if i == j:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())

sa=deque([])
en=deque([])
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        sa.append(b)
    elif b==N:
        en.append(a)
print('POSSIBLE' if any([x in en for x in sa]) else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

sa=[]
en=[]
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        sa.append(b)
    elif b==N:
        en.append(a)
print('POSSIBLE' if any([x in en for x in sa]) else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

g = [[0] * n for _ in range(n)]

for a, b in ab:
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1

ans = "IMPOSSIBLE"
for i, ele in enumerate(g[0]):
    if ele:
        if g[i][-1] == 1:
            ans = "POSSIBLE"
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(M):
    data.append([int(x) for x in stdin.readline().rstrip().split()])
shima = []

flag = False
for i in sorted(data):
    if i[0] == 1:
        shima.append(i[1])
    if (i[1] == N) and (i[0] in shima):
        flag = True
        break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
from_one = []
to_n = []

for _ in range(m):
    a, b = na()
    if a == 1:
        from_one.append(b)
    if b == n:
        to_n.append(a)

p = False
for i in from_one:
    if i in to_n:
        print("POSSIBLE")
        p = True
if not p:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
listA = []
listB = []
ans = "IMPOSSIBLE"
for i in range(m):
    a, b = map(int, input().split())
    maxAB = max(a, b)
    minAB = min(a, b)
    if minAB == 1 or maxAB == n:
        if minAB == 1:
            listA.append(maxAB)
            if listB.count(maxAB) == 1:
                ans = "POSSIBLE"
                break
        if maxAB == n:
            listB.append(minAB)
            if listA.count(minAB) == 1:
                ans = "POSSIBLE"
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
listA = []
listB = []
ans = "IMPOSSIBLE"
for i in range(m):
    a, b = map(int, input().split())
    maxAB = max(a, b)
    minAB = min(a, b)
    if minAB == 1:
        listA.append(maxAB)
        if listB.count(maxAB) == 1:
            ans = "POSSIBLE"
            break
    if maxAB == n:
        listB.append(minAB)
        if listA.count(minAB) == 1:
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
a = [sorted(map(int,input().split())) for _ in range(m)]
for i in range(n):
    if [1,i] in a and [i,n] in a:
        print("POSSIBLE")
        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)]
ab.sort()
mid = []
cand = []
mid_id = 0
for i in range(m):
  if ab[i][0] == 1:
    mid.append(ab[i][1])
  elif ab[i][0] == n or ab[i][1] == n:
    cand.append(ab[i])

if len(mid) == 0:
  print('IMPOSSIBLE')
  exit()
  
for j in range(len(cand)):
  if cand[j][0] in mid and cand[j][1] == n:
    print('POSSIBLE')
    exit()
  elif cand[j][1] in mid and cand[j][0] == n:
    print('POSSIBLE')
    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)]
mid = []
for i in range(m):
  if ab[i][0] == 1:
    mid.append(ab[i][1])
  elif ab[i][1] == 1:
    mid.append(ab[i][0])

for j in range(m):
  if ab[j][0] in mid and ab[j][1] == n:
    print('POSSIBLE')
    exit()
  elif ab[j][1] in mid and ab[j][0] == n:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

def main():
    N,M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    X1 = []
    for a in A:
        if a[0] == 1:
            X1.append(a)
    X2 = []
    for a in A:
        if a[1] == N:
            X2.append(a)
    for x1 in X1:
        for x2 in X2:
            if x1[1] == x2[0]:
                print("POSSIBLE")
                return
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

fst = []
scnd = []

for i in ab:
  if i[0]==1:
    fst.append(i[1])
  if N in i:
    scnd.append(i)

for i in scnd:
  for j in fst:
    if set(i) == set([j, N]):
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

fst = []

for i in ab:
  if i[0]==1:
    fst.append(i[1])

for i in ab:
  for j in fst:
    if set(i) == set([j, N]):
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = [int(x) for x in input().split()]
fst_to = deque([])
sec_from = deque([])
for a, b in [[int(x) for x in input().split()] for _ in range(M)]:
  if a == 1:
    fst_to.append(b)
  elif b == N:
    sec_from.append(a)
ret = 'IMPOSSIBLE'
for a in fst_to:
  if a in sec_from:
    ret = 'POSSIBLE'
    break
print(ret)

Submission status: Time Limit Exceeded

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

for i in range(m-1):
    for j in range(i+1,m):
        if ((a[i]|a[j])-(a[i]&a[j])) == {1,n}:
            print("POSSIBLE")
            exit()
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

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

s = []
e = []

for _ in range(M):
	tmp = list(map(int, input().split()))
	if 1 in tmp:
		s.append(max(tmp))
	elif N in tmp:
		e.append(min(tmp))

for ss in s:
	if ss in e:
		print("POSSIBLE")
		sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
ABs = list([list(map(int,input().split())) for _ in range(M)])
 
ship1 =[]
shipn =[]
 
for ab in ABs:
    if ab[0]==1:ship1.append(ab[1])
    elif ab[1]==N:shipn.append(ab[0])

jdg=False      
      
for j in ship1:
    if j in shipn:jdg=True
if jdg:print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ship1 =[]
shipn =[]

jdg=False      

for i in range(2,N):
    if [1, i] in ABs and [i, N] in ABs:jdg=True
      
if jdg:print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ship1 =[]
shipn =[]

for ab in ABs:
    if ab[0]==1:ship1.append(ab)
    elif ab[1]==N:shipn.append(ab)

jdg=False      
      
for _, j in ship1:
    if [j, N] in shipn:jdg=True
if jdg:print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(M)])
C = []
for a, b in ab:
    if a == 1:
        C.append(b)
    else:
        break
if len(C) == 0:
    print('IMPOSSIBLE')
    exit()
for c in C:
    if [c,N] in ab:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(M)])
c = []
for a, b in ab:
    if a == 1:
        c.append(b)
    if b == N:
        if a in c:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

atb  = [list(map(int, input().split())) for _ in range(M)]

flg  = 0
#愚直にやる
for i in range(2, N, 1):

    #定期便ある?
    if [1, i] in atb:
        if [i, N] in atb:
            print("POSSIBLE")
            flg = 1
if flg==0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    if c.count(i) == 2:
        print('POSSIBLE')
        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)]
ab.sort()
c = []

for i in range(M):
    if ab[i][0] == 1:
        c.append(ab[i][1])
    if ab[i][0] in c and ab[i][1] == N:
        print('POSSIBLE')
        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)]
ab.sort(reverse=True)
c = []

for i in range(M):
    if ab[i][1] == N:
        c.append(ab[i][0])
    if ab[i][1] in c:
        if ab[i][0] == 1:
            print('POSSIBLE')
            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)]
ab.sort()
c = []

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

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"
list1 = []
listN = []

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        list1.append(b)
    elif b == N:
        listN.append(a)

for i in range(1, N+1):
    if i in list1 and i in listN:
        ans = "POSSIBLE"
        break

print(ans)