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())
line = []

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
second = []

for l in line:
    if l[0] == start:
        second.append(l[1])
    elif l[1] == start:
        second.append(l[0])

for l in line:
    if l[0] in second:
        if l[1] == end:
            print('POSSIBLE')
            exit()
    if l[1] in second:
        if l[0] == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

    islands_to_1 = []
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1.append(max(boat))

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_1 in islands_to_1:
        if island_to_1 in islands_to_n:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    boats = []
    islands = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands.append(max(boat))

        boats.append(boat)

    for boat in boats:
        if boat[0] in islands:
            if boat[1] == n:
                print("POSSIBLE")
                return

        elif boat[1] in islands:
            if boat[0] == n:
                print("POSSIBLE")
                return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

s=[]
g=[]
for i, j in ab:
    if i==1:
        s.append(j)
    elif j==1:
        s.append(i)
    elif i==N:
        g.append(j)
    elif j==N:
        g.append(i)
flag=0
for i in range(len(s)):
    if s[i] in g:
        flag=1
        break

print("POSSIBLE"  if flag else "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=[]
g=[]
for i, j in ab:
    if i==1:
        s.append(j)
    elif j==1:
        s.append(i)
    elif i==N:
        g.append(j)
    elif j==N:
        g.append(i)
flag=0
for i in range(len(s)):
    for j in range(len(g)):
        if s[i]==g[j]:
            flag=1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def main():
    N, M = li_input()
    DL = [[] for _ in range(N + 1)]

    for i in range(M):
        a, b = li_input()
        DL[a].append(b)
        DL[b].append(a)

    i = 0
    R = [1]
    C = [1]

    while len(C) != 0 and i < 2:
        nC = []
        for c in C:
            for dl in DL[c]:
                if dl == N:
                    print("POSSIBLE")
                    return
                if dl not in R:
                    R.append(dl)
                    nC.append(dl)

        C = nC[:]
        i += 1

    print("IMPOSSIBLE")


main()

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
X = []
Y = []
for i in range(M):
    S, E = list(map(int, input().split()))
    if S == 1:
        X.append(E)
    if E == N:
        Y.append(S)
while 1:
    if X == [] or Y == []:
        print("IMPOSSIBLE")
        break
    min_x = min(X)
    min_y = min(Y)
    if min_x == min_y:
        print("POSSIBLE")
        break
    elif min_x > min_y:
        Y.remove(min_y)
    elif min_x < min_y:
        X.remove(min_x)
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = [0] * M
E = [0] * M
for i in range(M):
    S[i], E[i] = list(map(int, input().split()))
X = []
Y = []
for i in range(M):
    if S[i] == 1:
        X.append(E[i])
    if E[i] == N:
        Y.append(S[i])
while 1:
    if X == [] or Y == []:
        print("IMPOSSIBLE")
        break
    min_x = min(X)
    min_y = min(Y)
    if min_x == min_y:
        print("POSSIBLE")
        break
    elif min_x > min_y:
        Y.remove(min_y)
    elif min_x < min_y:
        X.remove(min_x)
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
S = [0] * M
E = [0] * M
for i in range(M):
    S[i], E[i] = list(map(int, input().split()))
X = []
Y = []
for i in range(M):
    if S[i] == 1:
        X.append(E[i])
    if E[i] == N:
        Y.append(S[i])
for i in range(len(X)):
    for j in range(len(Y)):
        if X[i] == Y[j]:
            print("POSSIBLE")
            break
    else:
        continue
    break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

flag = False
for i, j in itertools.product(range(0, m), range(0, m)):
    if a[i] == 1 and b[i] == a[j] and b[j] == n:
        flag = True

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
first, second = [], []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        first.append(b)
    if b == n:
        second.append(a)
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())
a = [list(map(int,input().split())) for i in range(M)]
b = []
c = []
for i in a:
    if i[0]==1:
        b.append(i)
    elif i[1]==N:
        c.append(i)
for i in b:
  for j in c:
    if i[1]==j[0]:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(" "))
first = []
second = []
flag = 0

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append(a)
  if a == 1:
    first.append(b)
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  for j in range(len(first)):
    for k in range(len(second)):
      if first[j] == second[k]:
        print("POSSIBLE")
        flag = 1
        break
  if flag == 0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(" "))
first = []
second = []
flag = 0

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append([a,b])
  if a == 1:
    first.append([a,b])
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  for j in range(len(first)):
    for k in range(len(second)):
      if first[j][1] == second[k][0]:
        print("POSSIBLE")
        flag = 1
        break
  if flag == 0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
dep = []
arr = []
ans = "IMPOSSIBLE"

for i in range(M):
  a,b = map(int ,input().split())
  if a == 1: dep.append(b-1)
  if b == N: arr.append(a-1)
 
for i in (arr):
  if i in dep:
    ans = "POSSIBLE"
    break
print(ans)

Submission status: Time Limit Exceeded

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

hop_before = []
hop_to = []

for i in range(M) :
    a, b = map(int, input().split())
    
    if a == 1 :
        hop_to.append(b)
    if b == N :
        hop_before.append(a)
        
contains = False
for i in sorted(hop_to) :
    for j in sorted(hop_before) :
        if j > i : continue
        if i == j :
            contains = True
            break

if contains == True :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

hop_before = []
hop_to = []

for i in range(M) :
    a, b = map(int, input().split())
    
    if a == 1 :
        hop_to.append(b)
    if b == N :
        hop_before.append(a)
        
contains = False
for i in hop_to :
    if i in hop_before :
        contains = True
        break

if contains == True :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

# 母体の削減を試みてみる
abM2 = []
for i in range(M):
    if abM[i][0] == 1 or abM[i][1] == N:
        abM2.append(abM[i])

transit = []
for i in range(len(abM2)):
    if abM2[i][0] == 1:
        transit.append(abM2[i][1])

for i in range(len(abM2)):
    if abM2[i][1] == N:
        if abM2[i][0] in transit:
            print("POSSIBLE")
            exit()
        
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

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

for i in range(M):
    if abM[i][1] == N:
        if abM[i][0] in transit:
            print("POSSIBLE")
            exit()
        
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

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

for i in range(M):
    if abM[i][0] in transit and abM[i][1] == N:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

startCheck = False
startST = []

for i in a:
    if i[0] == '1':
        startCheck = True
        startST.append(i[1])

if not startCheck:
    print('IMPOSSIBLE')
    exit()

for i in a:
    if i[0] in startST:
        if int(i[1]) == N:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M=map(int,input().split())
grid = []
for i in range(M):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
pre = []
pos = []
for ships in grid:
  if ships[0] == 1:
    pre.append(ships[1])
  if ships[1] == N:
    pos.append(ships[0])
if pre == [] or pos == []:
  print('IMPOSSIBLE')
  sys.exit()
pre.sort()
for islands in pre:
  if islands in pos:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
flag = 0
for i in ahoge:
    if i in hanege:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for element in input_list:
    if element[0] == 1:
        first_element.append(element[1])
    elif element[1] == N:
        second_element.append(element[0])

for i in first_element:
    if i in second_element:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def bfs(branch,n):
	arrival = [0 for i in range(n+1)]
	q = [1]
	arrival[q[0]] = 1
	while len(q) >= 1:
		for k in range(len(branch[q[0]])):
			if arrival[branch[q[0]][k]] == 0:
				arrival[branch[q[0]][k]] = arrival[q[0]] + 1
				q.append(branch[q[0]][k])
		q.pop(0)
	return arrival

n,m = map(int,input().split())
branch = dict()
for i in range(n):
	branch[i+1] = []
for i in range(m):
	a,b = map(int,input().split())
	branch[a].append(b)
	branch[b].append(a)

arrival = bfs(branch,n)
if arrival[n]-arrival[1] == 2:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m = list(map(int, sys.stdin.readline().split()))
ab = [[0, 0]]*m
for i in range(m):
    ab[i] = list(map(int, sys.stdin.readline().split()))

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

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

flag = False
for i in tmp:
    if i in tmp_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, c, d = [], [], []
for i in range(m):
    ab.append(list(map(int, input().split())))
for i in range(m):
    if(ab[i][0] == n):
        c.append(ab[i][1])
    elif(ab[i][1] == n):
        c.append(ab[i][0])
    elif(ab[i][0] == 1):
        d.append(ab[i][1])
    elif(ab[i][1] == 1):
        d.append(ab[i][0])
for i in c:
    if(i in d):
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    a, b = [], []
    to_n = []
    for _ in range(m):
        x, y = map(int, input().split())
        a.append(x)
        b.append(y)
        if y == n:
            to_n.append(x)

    for j in range(m):
        if a[j] == 1:
            if b[j] in to_n:
                return 'POSSIBLE'
    return 'IMPOSSIBLE'


print(main())

Submission status: Time Limit Exceeded

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

    for j in range(m):
        if a[j] == 1:
            if b[j] in to_n:
                return 'POSSIBLE'
    return 'IMPOSSIBLE'


print(main())

Submission status: Time Limit Exceeded

Solution code:
def judge(w1, w2):
	for i in range(0, len(w1)):
		if w1[i] in w2: return 'POSSIBLE'
	return 'IMPOSSIBLE'

N, M = map(int, raw_input().split())
way1 = []
way2 = []
for i in range(0, M):
	a, b = map(int, raw_input().split())
	if a == 1: way1.append(b)
	if b == N: way2.append(a)

print judge(way1, way2)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
    
aaa = 0
tbin_1 = []
tbin_n = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        tbin_1.append(xxx[1])
        if xxx[1] in tbin_n:
            aaa = 1
            break
            
    elif xxx[1] == n :
        tbin_n.append(xxx[0])
        if xxx[0] in tbin_1:
            aaa = 1
            break
    else:
        None


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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
    
aaa = 0
tbin_1 = []
tbin_n = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        tbin_1.append(xxx[1])
    elif xxx[1] == n :
        tbin_n.append(xxx[0])
    else:
        None
    if xxx[0] == 1 and xxx[1] in tbin_n:
        aaa = 1
        break
    elif xxx[1] == n and xxx[0] in tbin_1:
        aaa = 1
        break


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

Submission status: Time Limit Exceeded

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

tbin_1 = []
tbin_n = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        tbin_1.append(xxx[1])
    elif xxx[1] == n :
        tbin_n.append(xxx[0])
    else:
        None

aaa = 0
for i in tbin_1:
    if i in tbin_n:
        aaa = 1
        break

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
    
tbin_o = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1 or xxx[1] == n:
        tbin_o.append(xxx)



aaa = 0
for j in range(len(tbin_o)):
    for l in range(len(tbin_o)):
        if tbin_o[j][1] == tbin_o[l][0] and j != l:
            aaa = aaa + 1
            break
            
if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

tbin_2 = []
for i in range(len(tbin_o)):
    if tbin_o[i][0] == 1 or tbin_o[i][1] == n:
        tbin_2.append(tbin_o[i])

aaa = 0
for j in range(len(tbin_2)):
    for l in range(len(tbin_2)):
        if tbin_2[j][1] == tbin_2[l][0] and j != l:
            aaa = aaa + 1
            break
            
if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A,B,C = [],[],[]
Ans = "IMPOSSIBLE"
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
for i in range(M):
    if A[i] == 1:
        C.append(B[i])
for c in C:
    for i in range(M):
        if A[i] == c and B[i] == N:
            Ans = "POSSIBLE"
            break
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = (int(i) for i in input().split())
a,b = [0 for i in range(m)],[0 for i in range(m)]
g = [[0 for i in range(m)] for j in range(m)]
OK = False 
for i in range(m):
    a[i],b[i] = map(int, input().split())
    a[i]-=1
    b[i]-=1

for i in range(m):
    if a[i]==0:
        v = b[i]
        for j in range(m):
            if a[j]==v and b[j]==n-1:
                OK = True
print('POSSIBLE' if OK else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
t=[]
for _ in range(m):
    s,d=map(int,input().split())
    t.append((s,d))
t=sorted(t)
for s,d in t:
    if s!=1:
        print('IMPOSSIBLE')
        exit()
    if (d,n) in t:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
branch = dict()
for i in range(1,n+1):
	branch[i] = []
for i in range(m):
	a,b = map(int,input().split())
	branch[a].append(b)
	branch[b].append(a)
arrival = [0 for i in range(n+1)]
q = [1]
arrival[1] = 1
while len(q)>0:
	next = branch[q[0]]
	for i in range(len(next)):
		if arrival[next[i]] == 0:
			arrival[next[i]] = arrival[q[0]]+1
			q.append(next[i])
	q.pop(0)
if arrival[n] == 3:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
x.sort()
a = []
for i in x:
	if i[0]==1:
		a.append(i[1])
	else:
		break
for j in a:
	if [j,n] in x:
		m = 0
		print("POSSIBLE")
		break
if m != 0:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
[n,m] = list(map(int,input().split(' ')))
L1 = []
Ln = []
i=0
while i < m:
    l = list(map(int,input().split(' ')))
    if l[0] == 1:
        L1.append(l[1])
    elif l[1] == n:
        Ln.append(l[0])
    i += 1
q=0
for j in L1:
    if j in Ln:
        print("POSSIBLE")
        q = 1
        break
if q == 0:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
li1=[]
lin=[]
for i in range(m):
  a,b=map(int,input().split())
  if(a==1):li1.append(b)
  elif(b==1):li1.append(a)
  elif(a==n):lin.append(b)
  elif(b==n):lin.append(a)
for i in li1:
  if(i in lin):
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
      if(i==n-1):
        if(dist[i]==2):
          print("POSSIBLE")
          sys.exit()
        else:
          print("IMPOSSIBLE")
          sys.exit()
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  if(x==n-1 and dist[x]==2):
    print("POSSIBLE")
    sys.exit()
  elif(x==n-1 and dist[x]!=INF):
    print("IMPOSSIBLE")
    sys.exit()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m=map(int,input().split())
INF=10**15
d={}
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  d.setdefault(a,[]).append(b)
  d.setdefault(b,[]).append(a)
dist=[INF for i in range(n)]
dist[0]=0
queue=[]
for i in d[0]:
  queue.insert(0,i)
  dist[i]=1

while(len(queue)):
  x=queue.pop()
  for i in d[x]:
    if(dist[i]==INF):
      queue.insert(0,i)
      dist[i]=dist[x]+1
if(dist[-1]==2):print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
goal = []

for ship in ships:
    if n in ship:
        goal.append(ship[0])
    elif 1 in ship:
        relay.append(ship[1])

res = False
if len(goal) == 0 or len(relay) == 0:
    print("IMPOSSIBLE")
else:
    for i in relay:
        if i in goal:
            res = True
            break
    print("POSSIBLE" if res else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:

n,m = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(m)]
B = []
C = []
for i in A:
    if 1 in i:
        B += i

for i in A:
    a,b = i
    if a in B:
        C.append(b)
    elif b in B:
        C.append(a)
        


if n in C or n in B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
for ship in ships:
    if n in ship:
        judge = True
        relay.append(ship[0])

res = False
if judge is False:
    print("IMPOSSIBLE")
else:
    for i in relay:
        if [1, i] in ships:
            res = True
            break
    print("POSSIBLE" if res else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ships = [[int(x) for x in input().split()] for x in range(m)]

judge = False
relay = []
for ship in ships:
    if n in ship:
        judge = True
        relay.append(ship[0])

res = False
if judge is False:
    print("IMPOSSIBLE")
else:
    for i in relay:
        if [1, i] in ships:
            res = True
    print("POSSIBLE" if res else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

toN = list(filter(lambda x: N in x, AB))
toN = [flatten for inner in toN for flatten in inner]
frm_first = list(filter(lambda x: 1 in x, AB))
frm_first = [flatten for inner in frm_first for flatten in inner]

for v in frm_first:
    if v in toN:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

flag = 0
for k in c:
    if k == N:
        flag = 1
        break
    else:
        for i in range(M):
            if a[i] == k and b[i] == N:
                flag = 1
                break
    if flag == 1:
        break

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

Submission status: Time Limit Exceeded

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

array = []
for i in range(m):
    tmp = sorted([int(x) for x in input().split()])
    array.append(tmp)

determination = []
for j in range(len(array)):
    if array[j][0] == 1:
        determination.append(array[j][1])

res = False
for k in determination:
    for l in array:
        if k in l and n in l:
            res = True
            break
    if res:
        break
print("POSSIBLE" if res else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
Q = []
s = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        Q.append(P[i][1])
    else:
        s = i - 1
        break
if s >= 0:
    for j in range(s, M):
        if P[j][1] == N:
            if P[j][0] in Q:
                ans = ("POSSIBLE")
print(ans)

Submission status: Time Limit Exceeded

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

a = []
b = []
for i in range(int(M)):
    ab = input()
    c = ab.split(' ')
    a.append(c[0])
    b.append(c[1])

ans = 'IMPOSSIBLE'
for i in range(int(M)):
    if int(b[i]) == int(N):
        x = a[i]
        for j in range(int(M)):
            if int(b[j]) == int(x):
                y = a[j]
                if int(y) == 1:
                    ans = 'POSSIBLE'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import os
from collections import OrderedDict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right


class EndLoop(Exception):
    pass


def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            Deque1 = deque()
            DequeN = deque()
            edges_1 = [None] * N
            edges_N = [None] * N
            Deque1.extend(edges_1)
            DequeN.extend(edges_N)

            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                if a == 1:
                    Deque1[b - 1] = True
                elif b == 1:
                    Deque1[a - 1] = True
                elif a == N:
                    DequeN[b - 1] = True
                elif b == N:
                    DequeN[a - 1] = True
                else:
                    pass

            for i in range(N):
                if Deque1[i] == True and DequeN[i] == True:
                    print("POSSIBLE")
                    raise EndLoop

            print("IMPOSSIBLE")
            break
        except:
            break


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
from collections import OrderedDict, deque

def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            Deque1 = deque()
            DequeN = deque()
            edges_1 = [False] * N
            edges_N = [False] * N
            Deque1.extend(edges_1)
            DequeN.extend(edges_N)

            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                if a == 1:
                    Deque1[b - 1] = True
                elif b == 1:
                    Deque1[a - 1] = True
                elif a == N:
                    DequeN[b - 1] = True
                elif b == N:
                    DequeN[a - 1] = True
                else:
                    pass

            for i in range(N):
                if Deque1[i] == True and DequeN[i] == True:
                    print("POSSIBLE")
                    raise EndLoop

            print("IMPOSSIBLE")
            break
        except:
            break


solve()