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())
d = {}
for i in range(m):
    x, y = map(int, input().split())
    if x not in d.keys():
        d[x] = []
    d[x].append(y)
flag = False
for i in d.keys():
    if i == 1:
        l = d[i]
        for j in l:
            if j in d.keys():
                if n in d[j]:
                    flag = True
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

C = [i for i, x in enumerate(a) if x == 1]
D = [b[i] for i in C]
E = [i for i, x in enumerate(a) if x in D]
for i in E:
    if b[i] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
edges=[set() for i in range(n+1)]
for i in range(m):
	a,s=map(int,input().split())
	edges[a].add(s)
	edges[s].add(a)
for i in range(2,n):
	if i in edges[1]&edges[n]:
		print("POSSIBLE");exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:

def main():
    n,m = map(int,input().split())
    ab = [[0] * n for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1][b-1] = 1

    for mid in range(1,n):
        if ab[0][mid] == 1 and ab[mid][n-1] == 1:
            print('POSSIBLE')
            return
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    n,m = map(int,input().split())
    ab = [[0] * n for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1][b-1] = 1

    for mid in range(1,n):
        if ab[0][mid] == 1 and ab[mid][n-1]:
            print('POSSIBLE')
            return
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[[] for i in range(n+1)]
#r=[]*(n+1)
for i in range(m):
    ai,bi=map(int,input().split())
    if not bi in r[ai]:
        r[ai].append(bi)
        r[bi].append(ai)
yn=""
for i in range(2,n):
    if (i in r[1]) and (i in r[n]):
        print("POSSIBLE")
        yn="POSSIBLE"
        break
if yn=="":
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

flag = False
for i in range(len(ab)):
    for k in range(len(ab)-i):
        if ab[i][1] == ab[-k][0] or ab[i][0]==ab[-k][1]:
            print('POSSIBLE')
            flag = True
            break
    if flag:
        break
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())
    if a == 1 or b == N:
        ab.append([int(a), int(b)])

flag = False
for i in range(len(ab)):
    for k in range(len(ab)):
        if ab[i][1] == ab[k][0] or ab[i][0]==ab[k][1]:
            print('POSSIBLE')
            flag = True
            break
    if flag:
        break
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
#ab = []
aida = []
#start = []
for i in range(m):
    x, y = [int(j) for j in input().split()]
    if y == n:
        if x in aida:
            print("POSSIBLE")
            exit()
        else:
            aida.append(x)
    if x == 1:
        if y in aida:
            print("POSSIBLE")
            exit()
        else:
            aida.append(y)
    #ab.append((x, y))

"""
for i in range(len(start)):
    if start[i] in aida:
        print("POSSIBLE")
        exit()
"""
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
#ab = []
aida = []
#start = []
for i in range(m):
    x, y = [int(j) for j in input().split()]
    if y == n:
        if x in aida:
            print("POSSIBLE")
            exit()
        else:
            aida.append(x)
    if x == 1:
        if y in aida:
            print("POSSIBLE")
            exit()
        else:
            aida.append(y)
    #ab.append((x, y))

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
#ab = []
aida = []
start = []
for i in range(m):
    x, y = [int(j) for j in input().split()]
    if y == n:
        aida.append(x)
    if x == 1:
        start.append(y)
    #ab.append((x, y))

for i in range(len(start)):
    if start[i] in aida:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
ab = []
aida = []
for i in range(m):
    x, y = [int(j) for j in input().split()]
    if y == n:
        aida.append(x)
    ab.append((x, y))

for i in range(m):
    if ab[i][0] == 1 and ab[i][1] in aida:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

for i in range(m):
    if ab[i][0] == 1 and ab[i][1] in aida:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
first = []
for m in range(M):
    a, b = lr()
    if a == 1:
        first.append(b)
    A[m] = a
    B[m] = b
for i, b in enumerate(B):
    if b == N:
        if A[i] in first:
            print("POSSIBLE")
            exit(0)
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int,input().split())
ab = [[int(i) for i in input().split()] for _ in range(m)]
visited = [False]*n
visited[0] = True
q = []

for j in range(m):
    if ab[j][0]==1:
        q.append((ab[j][1]))
        visited[ab[j][1]-1] = True
            
while q:
    c = q.pop()
    for j in range(m):
        if ab[j][0]==c:
            visited[ab[j][1]-1] = True
print('POSSIBLE' if visited[n-1] else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
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 in range(m):
    if a[i] == 1:
        for j in range(m):
            if b[i] == a[j] and b[j] == n:
                print("POSSIBLE")
                exit()
    
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(m):
    if ab[i][0]==1:
        li.append(ab[i][1])

li=list(set(li))

for j in range(m):
    if ab[j][0] in li:
        if ab[j][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)]
li=[]

for i in range(m):
    if ab[i][0]==1:
        li.append(ab[i][1])

for j in range(m):
    if ab[j][0] in li:
        if ab[j][1]==n:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
r = [[0, 0] for _ in range(m)]
ln = []
l1 = []
for i in range(m):
    r[i][0], r[i][1] = map(int, input().split())
    if r[i][1] == n:
        ln.append(i)
    if r[i][0] == 1:
        l1.append(i)
ans = "IMPOSSIBLE"
for i in l1:
    for j in ln:
        if r[i][1] == r[j][0]:
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
first=[]
second=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        first.append(bi)
    elif bi==n:
        second.append(ai)
    fset,sset=set(first),set(second)
if len(list(fset&sset))>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
first=[]
second=[]
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if bi in second:
            ans="POSSIBLE"
            break
        else:
            first.append(bi)
    elif bi==n:
        if ai in first:
            ans="POSSIBLE"
            break
        else:
            second.append(ai)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
first=[]
second=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        first.append(bi)
    elif bi==n:
        second.append(ai)
ans="IMPOSSIBLE"
if len(first)!=0 and len(second)!=0:
    for i in first:
        if i in second:
            ans="POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

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

flag = False
for i in iki:
    if i in iki2:
        flag = True
        break
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

flag = False
for i in range(n):
    if graph[0][i] == 1:
        if graph[i][n-1] == 1:
            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 = []
for i in range(m):
	a, b = map(int, input().split())
	if b == n:
		c.append(a)
	ab.append([a,b])
ab.sort(key=lambda x: x[0])
for i in range(m):
	if ab[i][0] == 1:
		d = ab[i][1]
		if d in c:
			print ("POSSIBLE")
			exit()
print ("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(m)]
C = [b for a, b in AB if a == 1]
for a, b in AB:
  if a in C and b == n:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = [int(i) for i in input().split()]

connected_1 = []
connected_n = []
for i in range(m):
    a, b = [int(i) for i in input().split()]
    
    if a == 1:
        connected_1.append(b)
        
    if b == n:
        connected_n.append(a)

        
for i in range(len(connected_1)):
    if connected_1[i] in connected_n:
        print("POSSIBLE")
        break
    if i == len(connected_1)-1:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
A = 0
B = 1
mid = []
goalIndex = []
ab = []

n, m = map(int, input().split())
for i in range(m):
    a,b = map(int, input().split())
    ab.append([a, b])
    if a == 1:
        mid.append(b)
    elif b == n:
        goalIndex.append(i)

# for _ab in ab:
#     if _ab[B] == n and _ab[A] in mid:
#         print("POSSIBLE")
#         exit()

for m in mid:
    for g in goalIndex:
        if ab[g][A] == m:
            print("POSSIBLE")
            exit()            

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
A = 0
B = 1
mid = []
ab = []

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

for _ab in ab:
    if _ab[B] == n and _ab[A] in mid:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
a = 0
b = 1
mid = []
ab = []

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

# print(mid)

for _ab in ab:
    if _ab[b] == n and _ab[a] in mid:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab_list = [0] * m
for i in range(m):
	ab_list[i] = list(map(int, input().split()))
a_list = []
b_list = []
for i in ab_list:
	if i[0] == 1:
		a_list.append(i[1])
	elif i[1] == n:
		b_list.append(i[0])
r = 'IMPOSSIBLE'
for a in a_list:
	if a in b_list:
		r = 'POSSIBLE'
		break
print(r)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab_list = []
for i in range(m):
	ab_list.append(list(map(int, input().split())))
first_list = filter(lambda x: x[0] == 1, ab_list)
second_list = filter(lambda x: x[1] == n, ab_list)
f_list = list(map(lambda f:f[1], first_list))
s_list = list(map(lambda f:f[0], second_list))
r_list = filter(lambda x: x in s_list, f_list)
r = 'IMPOSSIBLE' if len(list(r_list)) == 0 else 'POSSIBLE'
print(r)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab_list = []
for i in range(m):
	ab_list.append(list(map(int, input().split())))
first_list = filter(lambda x: x[0] == 1, ab_list)
second_list = filter(lambda x: x[1] == n, ab_list)
f_list = list(map(lambda f:f[1], first_list))
s_list = list(map(lambda f:f[0], second_list))
r = 'IMPOSSIBLE'
for f in f_list:
	if f in s_list:
		r = 'POSSIBLE'
		break
print(r)

Submission status: Time Limit Exceeded

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

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

for i in lsta:
    if i in lstb:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

# 1から行ける島を列挙する
a = []
for x in l:
    if x[0] == 1:
        a.append(x[1])

# 1から行ける島からNからいける島があったらOK
for y in a:
    for z in l:
        if z[0] == y and z[1] == n:
            print ("POSSIBLE")
            exit ()
print ("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])

def calculate(n,m,arr):
    tmp = []
    tmp2 = []

    for ar in arr:
        f = ar[0]
        t = ar[1]
        if f == 1:
           tmp.append(t)
        if t == n:
           tmp2.append(f)

    res = False


    for tm in tmp:
        if tm == n:
            res = True
            break
        for tm2 in tmp2:
            if tm == tm2:
                res = True
                break

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




calculate(N,M,ARR)

Submission status: Time Limit Exceeded

Solution code:
S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])

def calculate(n,m,arr):
    tmp = []
    tmp2 = []

    for ar in arr:
        f = ar[0]
        t = ar[1]
        if f == 1:
           tmp.append(t)
        if t == n:
            tmp2.append(f)

    res = False
    for tm2 in tmp2:
        for tm in tmp:
            if tm == tm2:
                res = True
                break

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

calculate(N,M,ARR)

Submission status: Time Limit Exceeded

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

a_list = []
tmp_start = []
tmp_goal = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp_start.append(b)
    
    if b == n:
        tmp_goal.append(a)
    

    # 島1から意外の運航便のリスト
    #else:
    #    a_list.append([a, b])


for j in tmp_start:
    if j in tmp_goal:
        print('POSSIBLE')
        break

else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a_list = []
tmp = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp.append(b)
    
    # 島1から意外の運航便のリスト
    else:
        a_list.append([a, b])

a_list.sort(key=lambda x: x[0])
tmp.sort()
#print(a_list)
#print(tmp)

possible = 0
for b in tmp:
    #print(a_list)

    for j in range(len(a_list)):
        if len(a_list) == 1:
            if a_list[0][1] == n:
                possible = 1

        elif a_list[j][0] < b:
            a_list.pop(j)

        elif a_list[j][0] == b:
            if a_list[j][1] == n:
                possible = 1
                break
        else:
            break

if possible == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a1=[]
an=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.append(bi)
    elif bi==n:
        an.append(ai)

a1.sort()
an.sort()

flag = False

for i in range(len(a1)):
    if a1[i] in an:
        flag = True
        break
  
if flag==True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a1=[]
an=[]
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.append(bi)
    elif bi==n:
        an.append(ai)

a1.sort()
an.sort()

flag = False

for i in range(len(a1)):
    for j in range(len(an)):
        if a1[i]==an[j]:
            flag = True
            break
    if flag==True:
        break

if flag==True:
    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())
c = []
d = []
for i in range(m):
    
    if a[i] == 1:
        c.append(b[i])
    if b[i] == n:
        d.append(a[i])
ans = False
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    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())
c = []
d = []
for i in range(m):
    
    if a[i] == 1:
        c.append(b[i])
    if b[i] == n:
        d.append(a[i])
ans = False
c = list(set(c))
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [input().split() for i in range(m)]
c = []
d = []
for i in range(m):
    
    if int(a[i][0]) == 1:
        c.append(int(a[i][1]))
    elif int(a[i][1]) == n:
        d.append(int(a[i][0]))
ans = False
c = list(set(c))
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [input().split() for i in range(m)]
c = []
d = []
for i in range(m):
    if int(a[i][0]) == 1 and int(a[i][1]) == n:
        continue
    elif int(a[i][0]) == 1:
        c.append(int(a[i][1]))
    elif int(a[i][1]) == n:
        d.append(int(a[i][0]))
ans = False
c = list(set(c))
for i in c:
    if d.count(i) >=1:
        ans = True
        break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

a = [input().split() for i in range(m)]
c = []
d = []
for i in range(m):
    if int(a[i][0]) == 1 and int(a[i][1]) == n:
        continue
    elif int(a[i][0]) == 1:
        c.append(a[i][1])
    elif int(a[i][1]) == n:
        d.append(a[i][0])
ans = False
for i in range(len(c)):
    for j in range(len(d)):
        if c[i] == d[j]:
            ans = True
            break
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

for island in range(2,N):
    if (1,island) in ab and (island,N) in ab:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    A = [b for a, b in AB if a == 1]
    B = [a for a, b in AB if b == N]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    A = [ab for ab in AB if ab[0] == 1]
    B = [ab for ab in AB if ab[1] == N]

    result = 'IMPOSSIBLE'
    for a in A:
        for b in B:
            if a[1] == b[0]:
                result = 'POSSIBLE'
    print(result)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

go = []

for i in range(len(a)):
    if (a[i] == 1):
        go.append(b[i])
        a[i],b[i] == 0,0
u = 0
t = len(a)
while(u < t):
    if a[u] == 0:
        del(a[u])
        del(b[u])
        t -= 1
    if b[u] != n:
        del(a[u])
        del(b[u])
        t -= 1
    u += 1

for i in range(len(go)):
    for j in range(len(a)):
        if(go[i] == a[j]):
            if(b[j] == n):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

go = []

for i in range(len(a)):
    if (a[i] == 1):
        go.append(b[i])

for i in range(len(go)):
    for j in range(len(a)):
        if(go[i] == a[j]):
            if(b[j] == n):
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
tmp=0
ab=[]
indexk=[]
k={}

for i in range(m):
  x=list(map(int,input().split()))
  ab.append(x)
ab.sort()
for i in range(m):
  if ab[i][0]==1:
    k[i]=ab[i][1]
    indexk.append(i)

for i in indexk:
  for j in range(len(k),m):
    if k[i]==ab[j][0] and ab[j][1]==n:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
tmp=0
ab=[]
indexk=[]
k={}

for i in range(m):
  x=list(map(int,input().split()))
  ab.append(x)
  if x[0]==1:
    k[i]=x[1]
    indexk.append(i)

for i in indexk:
  for j in range(m):
    if k[i]==ab[j][0] and ab[j][1]==n:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def ABC068C():
    N, M = map(int, input().split())
    ship_first = []
    ship_second = []
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            if b == N:
                print('POSSIBLE')
                return
            else:
                ship_first.append(b)
        elif b == N:
            ship_second.append(a)

    for i in ship_first:
        if i in ship_second:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
    return

ABC068C()

Submission status: Time Limit Exceeded

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

ab1 = []
ab2 = []

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

for i in ab1:
    for j in ab2:
        if i == j:
            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):
  a,b=map(int,input().split())
  if a==1:
    first.append(b)
  elif b==N:
    second.append(a)
 
ans="IMPOSSIBLE"
    
for i in first:
  if i in second:
    ans="POSSIBLE"
    break
 
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)
  elif b==N:
    second.append(a)

ans="IMPOSSIBLE"
    
for i in first:
  if i in second:
    ans="POSSIBLE"
    break

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 and b!=N:
    continue
  elif a==1:
    first.append(b)
  else:
    second.append(a)

for i in first:
  if i in second:
    ans="POSSIBLE"
    break
  else:
    ans="IMPOSSIBLE"

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)
  elif b==N:
    second.append(a)

for i in first:
  if i in second:
    ans="POSSIBLE"
    break
  else:
    ans="IMPOSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse import coo_matrix

n, m = map(int, input().split())
a = np.empty(m, dtype=np.int)
b = np.empty(m, dtype=np.int)
for i in range(m):
    a[i], b[i] = map(lambda x: int(x)-1, input().split())

g = coo_matrix((np.ones(m, dtype=np.int8), (a, b)), (n, n)).tolil()
res = 'IMPOSSIBLE'
for i in range(n):
    if g[i, n-1] == 0:
        continue
    if g[0, i] == 1:
        res = 'POSSIBLE'
        break

print(res)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.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 = [list(map(int, input().split())) for i in range(M)]
second = []
flag = False
for x in range(M):
    if ab[x][0] == 1:
        second.append(ab[x][1])

for y in range(len(second)):
    for z in range(M):
        if ab[z][0] == second[y] and ab[z][1] == N:
            flag = True
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
tmp = 0
flg = 0
a = []
for i in range(m):
  x,y = map(int, input().split())
  if x == 1:
    tmp = y
  elif y == n:
    tmp = x
  if tmp != 0 and a.count(tmp) == 0:
    a.append(tmp)
  elif tmp != 0 and a.count(tmp) >= 1:
    flg = 1
  tmp = 0
if flg == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
ab = []
for i in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))

fl = False
for i,j in ab:
    if i!=1:
        continue
    for k,l in ab:
        if i==1 and (j!=k or l!=N):
            continue
        else:
            fl = True
print('POSSIBLE') if fl else print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
ab = []
for i in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
ab.sort(key=itemgetter(0))

fl = False
for i,j in ab:
    if i!=1:
        continue
    for k,l in ab:
        if i==1 and (j!=k or l!=N):
            continue
        else:
            fl = True
print('POSSIBLE') if fl else print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = input().split()
N = int(N)
M = int(M)

# 2 boat
boat = 2
ab = np.zeros(M)
ab1 = []
abN = []
ok = "IMPOSSIBLE"
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ab1.append(b)
    elif b == N:
        abN.append(a)
for b in ab1:
    for a in abN:
        if a == b:
            ok = "POSSIBLE"
print(ok)

Submission status: Time Limit Exceeded

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

# 2 boat
boat = 2
ab = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    ab.append((a,b))
import numpy as np
ab = np.array(ab)
ok = "IMPOSSIBLE"
for a1 in ab[ab.T[0]==1]:
    # 1 to target N-> ok
    for abbb in ab[ab.T[0]==a1[1]]:
        if abbb[1] == N:
            ok = "POSSIBLE"
            break
print(ok)