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:
# -*- coding:utf-8 -*-

def solve():
    N, M = list(map(int, input().split()))
    """
    from1 := 1から行ける島番号のリスト
    toN := Nに行ける島番号のリスト
    from1とtoNの両方に同じ島番号が存在するとき、POSSIBLE
    """
    from1, toN = [], []
    for i in range(M):
        a, b = list(map(int, input().split()))
        if a == 1:
            from1.append(b)
        elif b == N:
            toN.append(a)
    
    for b in from1:
        if b in toN:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")
        

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
A,B = [],[]
AtN,Bf1 = [],[]
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        Bf1 += [b]
    elif b == N:
        AtN += [a]

if (any((b in AtN) for b in Bf1)):
    print("POSSIBLE")
else:
    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)]
judge = False
m = []
for i, (a, b) in enumerate(ab):
    if a == 1:
        m.append(b)

for i, (a, b) in enumerate(ab):
    if a in m and b == N:
        judge = True
        break

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

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def main():
  N,M = map(int, input().split())
  route1 = []
  routeN = []
  for _ in range(M):
    ab = sorted(list(map(int, input().split())))
    if ab[0] == 1:
      route1.append(ab[1])
    elif ab[1] == N:
      routeN.append(ab[0])

  for i in route1:
    if i in routeN:
      return True
  return False

if __name__ == "__main__":
  if main():
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')

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

# N in b    
indices = [i for i, x in enumerate(b) if x == N]
# matched b of a in b
for i in range(len(indices)):
#    print(a[indices[i]])
#    print(b[indices[i]])
    
    indices_2 = [ii for ii, x in enumerate(b) if x == a[indices[i]]]
    
#    print(indices_2)
    
    if len(indices_2) == 0:
        continue
    
    for j in range(len(indices_2)):
#        print(indices_2)
#        print(a[indices_2[j]])
        
        if a[indices_2[j]] == 1:
            print('POSSIBLE')
            quit()
            
print('IMPOSSIBLE')

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())
if N in b and 1 in a:
    for i in range(M):
        for j in range(M):
            if a[j] == 1 and b[i] == N and a[i] == b[j]:
                print('POSSIBLE')
                exit()
            else:
                pass
print('IMPOSSIBLE')

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())
for i in range(M):
    for j in range(M):
        if a[j] == 1 and b[i] == N and a[i] == b[j]:
            print('POSSIBLE')
            exit()
        else:
            pass
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/abc068/tasks/arc079_a
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
flag = False
tmp = -1
for i in range(M):
    if ab[i][0] == N:
        tmp = ab[i][1]
        for j in range(M):
            if ab[j][0] == tmp and ab[j][1] == 1:
                flag = True
                break
            if ab[j][1] == tmp and ab[j][0] == 1:
                flag = True
                break


    if ab[i][1] == N:
        tmp = ab[i][0]
        for j in range(M):
            if ab[j][0] == tmp and ab[j][1] == 1:
                flag = True
                break
            if ab[j][1] == tmp and ab[j][0] == 1:
                flag = True
                break


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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v,depth):
    # ノードに訪れた
    visited[v] = 1
    if depth == 2:
        return
    for a, b in sides:
        if v == a-1:
            depth += 1
            dfs(b-1, depth)
            depth -= 1

n, m = MI()
sides = [LI() for _ in range(m)]
visited = [0] * n
dfs(0,0)
print('POSSIBLE') if visited[n-1] == 1 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)]

S = []
E = []

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

#print(S)
#print(E)

flag = False
for s in S:
  if s in E:
    flag = True
    break

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    s, n = map(int, input().split())
    if s == 1:
        edge1.append(n)
    elif n == N:
        edgeN.append(s)
for e1 in edge1:
    if e1 in edgeN:
        print('POSSIBLE')
        quit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    e = list(map(int, input().split()))
    if e[0] == 1:
        edge1.append(e[1])
    elif e[1] == N:
        edgeN.append(e[0])
for e1 in edge1:
    if e1 in edgeN:
        print('POSSIBLE')
        quit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l1=[]
l2=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    l1.append(b)
  if b==n:
    l2.append(a)
b=False
for i in range(2,n):
  if i in l1 and i in l2:
    b=True
if b:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


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

ans = False
routes = {}
for i in range(N):
    routes[i+1] = []
for ai in range(len(a)):
    x,y = a[ai]
    if 1 in a[ai]:
        routes[1] = routes[1]+a[ai]
    if N in a[ai]:
        routes[N] = routes[N]+a[ai]

# print(routes)
if 1 in routes[N] or N in routes[1]:
    print("POSSIBLE")
    exit()

s_reach = list(set(routes[1]))
N_reach = list(set(routes[N]))
Ms_reach = list(set(N_reach+s_reach))

if len(s_reach)+len(N_reach) != len(Ms_reach):
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc068/tasks/arc079_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect

def main():
    N, M = map(int, input().split())
    s_list = []
    g_list = []

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

    for s in s_list:
        if s in g_list:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

ans = 'IMPOSSIBLE'
for i in range(M):
    if AB[i][1] == N:
        if AB[i][0] in A1:
            ans = 'POSSIBLE'

print(ans)

Submission status: Time Limit Exceeded

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

A1 = [1]
B4 = [4]
for i in range(M):
    if AB[i][0] == 1:
        A1.append(AB[i][1])
    if AB[i][1] == N:
        B4.append(AB[i][0])

ans = 'IMPOSSIBLE'
for a in A1:
    if a in B4:
        ans = 'POSSIBLE'
        break

print(ans)

Submission status: Time Limit Exceeded

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

A1 = [1]
B4 = [4]
for i in range(M):
    if AB[i][0] == 1:
        A1.append(AB[i][1])
    if AB[i][1] == N:
        B4.append(AB[i][0])

ans = 'IMPOSSIBLE'
for a in A1:
    if a in B4:
        ans = 'POSSIBLE'

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()
X,Y=[],[]
for i in range(M):
	a = LI()
	if a[0] == 1:
		X.append(a[1])
	if a[1] == N:
		Y.append(a[0])
	
for x in X:
	if x in Y:
		print("POSSIBLE")
		exit()
	

	
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()

AB=[LI() for i in range(M)]
X=[]
for ab in AB:
	if ab[0] == 1:
		X.append(ab[1])
for ab in AB:
	if ab[1] == N:
		if ab[0] in X:
			print("POSSIBLE")
			exit()
	
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
list1 = []
list2 = []
for i in range(M):
    a = [int(x) for x in input().split()]
    list1.append(a[0])
    list2.append(a[1])
flag = 0
for i, x in enumerate(list1):
    if x == 1:
        new = list2[i]
        for k,j in enumerate(list1):
            if j == new:
                if list2[k] == N:
                    flag = 1
                    break
            
        for k,j in enumerate(list2):
            if j == new:
                if list1[k] == N:
                    flag = 1
                    break
            
for i, x in enumerate(list2):
    if x == 1:
        new = list1[i]
        for k,j in enumerate(list1):
            if j == new:
                if list2[k] == N:
                    flag = 1
                    break
            
        for k,j in enumerate(list2):
            if j == new:
                if list1[k] == N:
                    flag = 1
                    break
if flag == 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#21:06
N,M=map(int,input().split())
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
first=[]
last=[]

for t in l:
    if t[0]==1:
        first.append(t[1])
    elif t[1]==N:
        last.append(t[0])
flag=False
for s in first:
    if s in last:
        flag=True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split());a,b=[],[]
for i in range(m):
  aa,bb=map(int,input().split())
  a.append(aa);b.append(bb)
c=[]
for i in range(m):
  if a[i]==1:c.append(b[i])
for i in range(m):
  if b[i]==n:
    if a[i] in c:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def Dijkstra(N, edges, s):
    from heapq import heappush, heappop, heapify
    dist = [10**20 for _ in range(N)]
    dist[s], h = 0, [[0, s]]
    while (len(h)):
        p = heappop(h)
        d, v = p[0], p[1]
        if d > dist[v]:
            continue
        for i in range(len(edges[v])):
            u = edges[v][i]
            if d + 1 < dist[u]:
                dist[u] = d + 1
                heappush(h, [dist[u], u])
    return dist

N, M = map(int, input().split())
es = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    es[a].append(b)
    es[b].append(a)
dist = Dijkstra(N, es, 0)
if dist[N - 1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
judge = 0 #0:不可,1:可

if(M >= 2):
 #N*N行列 島a~b間に定期便あり:1,なし:0
 island = []
 for i in range(N):
  island.append([0]*N)

 island1 = []
 for i in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  island[a][b] = 1
  island[b][a] = 1
  if(a == 0):
    island1.append(b)
  elif(b == 0):
    island1.append(b)

 for i in island1:
  if(island[i][N-1] == 1):#配列(リスト)の要素のアクセスO(1)
    judge = 1
    break
    
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
judge = 0 #0:不可,1:可

#島1 -> 島N
island = []
island1 = [] #島1の定期便
for i in range(M):
  a,b = map(int,input().split())
  island.append([a,b])
  if(a == 1):
    island1.append(b)
  if(b == 1):
    island1.append(a)
    
for i in range(len(island)):#TLEの可能性しかない
 for j in range(len(island1)):
   if(island[i][0] == island1[j]):
     if(island[i][1] == N):
      judge = 1
      break
   if(island[i][1] == island1[j]):
     if(island[i][0] == N):
      judge = 1
      break
      
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N , M = map(int, input().split())
ablist = [list(map(int,input().split())) for _ in range(M)]
optlist = []
flg = False
for ab in ablist:
    if ab[1] == N:
        optlist.append(ab[0])
for ab in ablist:
    if (ab[0] == 1) and  (ab[1] in optlist):
        flg = True
print("POSSIBLE" if flg else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, (input().split()))
L = [[0 for i in range(N)] for j 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
#print(L)
for i in range(N):
    if L[0][i] == 1:
        if L[i][N - 1] == 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

A = []
B = []

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

ans = 'IMPOSSIBLE'
for a in A:
    if a in B:
        ans = 'POSSIBLE'
        break
print(ans)

Submission status: Time Limit Exceeded

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

A = []
B = []
x = []

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

ans = 'IMPOSSIBLE'
for a in A:
    for b in B:
        if a == b:
            ans = 'POSSIBLE'
            break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())
a, b = [0]*M, [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
for i, x in enumerate(b):
    if x == N:
        for j, y in enumerate(a):
            if y == 1 and b[j] == a[i]:
                print('POSSIBLE')
                sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/23
Solved on 2019/3/
@author: shinjisu
"""


# ABC 068 C - Cat Snuke and a Voyage

def getInt(): return int(input())

def getIntList(): return [int(x) for x in input().split()]

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    N, M = getIntList()
    d.dmp((N, M), 'N, M')
    ship = []
    for i in range(M):
        a, b = getIntList()
        ship.append((a, b))
    d.dmp((ship), 'ship')
    for i in range(2, N):
        if ((1, i) in ship or (i, 1) in ship) and\
             ((i, N) in ship or (N, 1) in ship):
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
First = []
Second = []
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        First.append(b)
    if b == n:
        Second.append(a)
for i in range(1,n+1):
    if i in First and i in Second:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
First = []
Second = []
for i in range(m):
    ab = [int(j) for j in input().split()]
    if ab[0] == 1:
        First.append(ab)
    if ab[1] == n:
        Second.append(ab)
if any (i[1]==j[0] for i in First for j in Second):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=[int(i) for i in input().split()]
a_to=deque([])
to_b=deque([])
for i in range(m):
    a,b=[int(i) for i in input().split()]
    if a==1:
        a_to.append(b)
    if b==n:
        to_b.append(a)
for i in a_to:
    if i in to_b:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(i) for i in input().split()]
voyage=[tuple(int(i) for i in input().split()) for _ in range(m)]
for i in range(m):
    if voyage[i][0]==1:
        if (voyage[i][1],n) in voyage:
            print("POSSIBLE")
            break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)

Submission status: Time Limit Exceeded

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

ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)
exit()

Submission status: Time Limit Exceeded

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

ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)

Submission status: Time Limit Exceeded

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

ab0 = []
abn = []
res="IMPOSSIBLE"
for x in ab:
    if x[0] == 0:
        if x[1] in abn:
            res= "POSSIBLE"
            break
        ab0.append(x[1])
    if x[1] == n-1:
        if x[0] in ab0:
            res= "POSSIBLE"
            break
        abn.append(x[0])

print(res)

Submission status: Time Limit Exceeded

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

ab0 = []
abn = []
for x in ab:
    if x[0] == 0:
        ab0.append(x[1])
    if x[1] == n-1:
        abn.append(x[0])

res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break

print(res)

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 )


firstBoat = []
secondBoat = []
for i in range(M):
    if a[i] == 1: firstBoat.append( b[i] )
    if b[i] == N and a[i] != 1: secondBoat.append( a[i] )

ans = False
for f in firstBoat:
    for s in secondBoat:
        if f == s:
            ans = True
            break

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

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 )


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

ans = False
for f in firstBoat:
    for s in secondBoat:
        if f == s:
            ans = True
            break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
check_1 = list(set(check_1))
chek_N = list(set(check_N))

flag = False
for i in sorted(check_1):
    if i in check_N:
        flag = True
        break
        
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
flag = False
for i in sorted(set(check_1)):
    if i in check_N:
        flag = True
        break
        
if flag:
    print('POSSIBLE')
else:
    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())
    ab.append((a,b))
check_N = []
check_1 = []
for i in ab:
    if i[1] == N:
        check_N.append(i[0])
    if i[0] == 1:
        check_1.append(i[1])
        
flag = False
for i in sorted(set(check_1)):
    if i in check_N:
        flag = True
        break
        
if flag:
    print('POSSIBLE')
else:
    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())
    ab.append((a,b))
    
check_N = []
check_1 = []
for i in ab:
    if i[1] == N:
        check_N.append(i[0])
    if i[0] == 1:
        check_1.append(i[1])
        
flag = False
for i in check_1:
    if check_N.count(i) >= 1:
        flag = True
        break
        
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = []
for i in range(M):
  a,b = IL()
  if a == 1:
    if b in data:
      print("POSSIBLE")
      break
    else:
      data.append(b)
  if b == N:
    if a in data:
      print("POSSIBLE")
      break
    else:
      data.append(a)
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

data = []
for a,b in ab:
  if a == 1:
    if b in data:
      print("POSSIBLE")
      break
    else:
      data.append(b)
  if b == N:
    if a in data:
      print("POSSIBLE")
      break
    else:
      data.append(a)
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ab.sort()
data = []
for a,b in ab:
  if a == 1:
    data.append(b)
  else:
    break

for i in range(M-1,-1,-1):
  a = ab[i][0]
  if a in data and ab[i][1] == N:
    print("POSSIBLE")
    break
  elif a==1:
    print("IMPOSSIBLE")
    break

Submission status: Time Limit Exceeded

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

data = []
for a,b in ab:
  if a == 1:
    data.append(b)

for a,b in ab:
  if a in data and b == N:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in range(len(first)):
    if first[i] in second:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	if I[1]==N:
		C.append(I[0])
		D.append(I[1])
for b in B:
	for c in C:
		if b==c:
			print('POSSIBLE')
			exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
for m in range(M):
	I=list(map(int,input().split()))
	A.append(I[0])
	B.append(I[1])
tA=[]
tB=[]
for i,x in enumerate(A):
	if x==1:
		tA.append(B[i])
for i,x in enumerate(B):
	if x==N:
		if A[i] in tA:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
for m in range(M):
	I=list(map(int,input().split()))
	A.append(I[0])
	B.append(I[1])
tA=[]
tB=[]
for i,x in enumerate(A):
	if x==1:
		tA.append(B[i])
for i,x in enumerate(B):
	if x==N:
		tB.append(A[i])
for a in tA:
	if a in tB:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
for m in range(M):
	I=list(map(int,input().split()))
	A.append(I[0])
	B.append(I[1])
def DP(next,c):
	global N,A,B
	r=-1
	if c==3:
		return -1
	if c==2 and next==N:
		return 1
	for i,x in enumerate(A):
		if x==next:
			r=max(r,DP(B[i],c+1))
	for i,x in enumerate(B):
		if x==next:
			r=max(r,DP(A[i],c+1))
	return r

if DP(1,0)==1:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
b = [x[1] for x in l if x[0]==1]
a = [x[0] for x in l if x[1]==n]
for i in b:
    if i in a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
lst = set()
fst = set()
for i in range(m): 
  r = list(map(int,input().split()))
  if r[1] == n:
    lst.add(r[0])
  elif r[0] == 1:
    fst.add(r[1])
  if len(lst & fst) != 0:
    break
print('IMPOSSIBLE' if len(fst & lst) == 0 else 'POSSIBLE')