Problem:


Score : 300 points

Problem Statement

In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.

There are M kinds of regular boat services between these islands.
Each service connects two islands. The i-th service connects Island a_i and Island b_i.

Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.

Help him.

Constraints

3 ≤ N ≤ 200 000

1 ≤ M ≤ 200 000

1 ≤ a_i < b_i ≤ N

(a_i, b_i) \neq (1, N)

If i \neq j, (a_i, b_i) \neq (a_j, b_j).

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

You have to use three boat services to get to Island 4.

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

5 5
1 3
4 5
2 3
2 4
1 4

Sample Output 4

POSSIBLE

You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
ans="IMPOSSIBLE"
f=False
for i in range(m):
		a,b=map(int,input().split(" "))
		if a==1:l.append(b)
		if b==n:bone.append(a)
for i in l:
	for j in bone:
		if i == j:
			ans="POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

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

def cat_snuke():	
	for i in l:
		for j in bone:
			if i == j:
				print("POSSIBLE")
				return 0
		
	print("IMPOSSIBLE")

cat_snuke()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
ans=False
for i in range(m):
	a,b=map(int,input().split(" "))
	if a==1:l.append(b)
	if b==n:bone.append(a)

l.sort()
bone.sort()
for i in l:
	for j in bone:
		if i == j:
			ans=True
	
if ans == True:print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
one_count=[]
count=0
for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if a==1:one_count.append(count)
	count=count+1
	if b==n:bone.append(a)
	count=count+1
	
def cat_snuke():
	for i in one_count:
		for j in bone:
			if l[i+1] == j:
				print("POSSIBLE")
				return 0
	print("IMPOSSIBLE")		
cat_snuke()

Submission status: Time Limit Exceeded

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

for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if b==n:
		bone.append(a) #nと定期便がある島を記録	
def cat_snuke():
	count = 0
	for i in l:
		if i==1:
			for j in bone:
				if l[count+1] == j:
					print("POSSIBLE")
					return 0
		count=count+1
	print("IMPOSSIBLE")
		
cat_snuke()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
count = 0
ans="IMPOSSIBLE"
for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	
	if b==n:
		bone.append(a) #nと定期便がある島を記録
for i in l:
	if i==1:
		for j in bone:
			if l[count+1] == j:
				ans="POSSIBLE"
				break
	count=count+1
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
 
arr = []
i = 0
for i in range(M):
    append = arr.append
    t = list(map(int, input().split(" ")))
    append(t)
p1 = [x for x in arr if x[0] == 1]
 
ii = 0
iii = 0
r = 0
for ii in p1:
    for iii in arr:
        if iii[0] == ii[1]:
            if iii[1] == N:
                r = 1
                break
        if r != 0:
            break

if (r != 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(x) for x in input().split()]
set1=set()
setn=set()
for i in [None]*M:
    ipt=[int(x) for x in input().split()]
    if 1 in ipt:
        set1 = set1.union(ipt)
    if N in ipt:
        setn = setn.union(ipt)
if set1 & setn:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys 

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

res = 'IMPOSSIBLE'

for i in b:
  for k in range(M):
    if a[k][0] == a[i][1] and a[k][1] == N:
         res = 'POSSIBLE'
         break

print (res)

Submission status: Time Limit Exceeded

Solution code:
import sys 

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

res = 'IMPOSSIBLE'

for i in b:
  for k in range(M):
    if a[k][0] == a[i][1]:
      if a[k][1] == N:
         res = 'POSSIBLE'
         break

print (res)

Submission status: Time Limit Exceeded

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

res = 'IMPOSSIBLE'

for i in b:
  for k in range(M):
    if a[k][0] == a[i][1]:
      if a[k][1] == N:
         res = 'POSSIBLE'
print (res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
flag=0
for i in range(M):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    if x==1:
        c.append(y)
for i in range(M):
    if b[i]==N:
        if a[i] in c:
            flag=1
if flag==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Time Limit Exceeded

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

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

ans = "IMPOSSIBLE"
for i in island[0]:
    if i in island[n-1]:
        ans = "POSSIBLE"
        break

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = "IMPOSSIBLE"
for i in island[0]:
    if i in island[n-1]:
        ans = "POSSIBLE"


print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

print()

if N - 1 in set(sum(ends, [])):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

print()

if N - 1 in sum(ends, []):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
from scipy.sparse import*
f=lambda*z:map(int,raw_input().split());n,m=f();a,b=zip(*map(f,[0]*m))
g=csgraph.dijkstra(csr_matrix(([1]*m,(a,b)),[n+1]*2),1,1)
print 'POSSIBLE' if g[n]==2 else 'IMPOSSIBLE'

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ship = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or b == n:
        ship.append((a, b))
if len(ship) == 0:
    print("IMPOSSIBLE")
    exit()

ship.sort()
i = 0

while ship[i][0] == 1:
    i += 1
    if i == len(ship):
        print("IMPOSSIBLE")
        exit()

for j in range(i):
    for k in range(i, len(ship)):
        if ship[j][1] == ship[k][0]:
            print("POSSIBLE")
            exit()
        elif ship[j][1] < ship[k][0]:
            break

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n = input().split()
tmpList = [0,0]
aList = []
bList = []
judge = "IMPOSSIBLE"
for i in range(int(n[1])):
    tmpList = input().split()
    aList.append(int(tmpList[0]))
    bList.append(int(tmpList[1]))

aindexes = [i for i, x in enumerate(aList) if x == 1]

for i in aindexes:
    bindexes = [j for j, x in enumerate(aList) if x == bList[i]]
    for k in bindexes:
        if bList[k] == int(n[0]):
            judge = "POSSIBLE"

print(judge)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
ship = [[] for i in range(2)]
data=[]
for i in range(M):
    data.append(list(map(int,input().split())))
    a = data[i][0]
    b = data[i][1]
    if b == N and (a in ship[1])==False:
        ship[1].append(a)
        if a in ship[0]:
            print("POSSIBLE")
            break
    if a == 1 and (b in ship[0])==False:
        ship[0].append(b)   
        if b in ship[1]:
            print("POSSIBLE")
            break
    if i == M-1:
        print("IMPOSSIBLE")
#data = [list(map(int,input().split())) for i in range(M)]
#ship = [[] for i in range(2)]

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    args = sys.stdin.readline().split()
    N = int(args[0])
    M = int(args[1])
    src_list = {}
    dst_list = {}
    for i in range(M):
        args = sys.stdin.readline().split()
        src_list[i] = int(args[0])
        dst_list[i] = int(args[1])

    relay_points = set()
    for i in range(M):
        if src_list[i] == N:
            relay_points.add(dst_list[i])
        if dst_list[i] == N:
            relay_points.add(src_list[i])

    for i in range(M):
        for num in relay_points:
            if src_list[i] == num:
                if dst_list[i] == 1:
                    print('POSSIBLE')
                    sys.exit()
            if dst_list[i] == num:
                if src_list[i] == 1:
                    print('POSSIBLE')
                    sys.exit()


    print('IMPOSSIBLE')

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
X=input().split()
N=int(X[0])
M=int(X[1])
A=[]
B=[]
C=[]
count=0
for i in range(M):
 Y=input().split()
 a=int(Y[0])
 b=int(Y[1])
 A.append(a) 
 B.append(b) 
for i in range(M):
 if(A[i]==1):
   C.append(B[i])
n=len(C)
for i in range(n):
 for j in range(M):
  if((C[i]==A[j])and(B[j]==N)): 
   count +=1
if(count==0):
 print("IMPOSSIBLE")
else:
 print("POSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !
a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
#print(in2)
#print(out2)
len_in2=len(in2)
for q in range(len_in2):
    if in2[q] in out2:
        print("POSSIBLE")
        break
    elif q+1==len_in2:
        print("IMPOSSIBLE")
    else:
        continue

Submission status: Time Limit Exceeded

Solution code:
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if b == N:
        nlist.append(a)
    if a == 1:
        list1.append(b)
for i in list1:
    if i in nlist:
        print('POSSIBLE')
        flag = False
        break
if flag:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if b == N:
        nlist.append(a)
    if a == 1:
        list1.append(b)
for i in list1:
    if i in nlist:
        print('POSSIBLE')
        flag = False
if flag:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

arr = []
i = 0
for i in range(M):
    append = arr.append
    t = list(map(int, input().split(" ")))
    append(t)
p1 = [x for x in arr if x[0] == 1]

ii = 0
iii = 0
r = 0
for ii in p1:
    for iii in arr:
        if iii[0] == ii[1]:
            if iii[1] == N:
                r = 1
                break

if (r != 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
X=input().split()
N=int(X[0])
M=int(X[1])
A=[]
B=[]
C=[]
count=0

for i in range(M):
 Y=input().split()
 a=int(Y[0])
 b=int(Y[1])
 A.append(a) #A[i]=a[i]
 B.append(b) #B[i]=b[i]

for i in range(M):
 if(A[i]==1):
   C.append(B[i]) #島1から島Xへいく船についてXの値を格納
n=len(C)

for i in range(n):
 for j in range(M):
  if((C[i]==A[j])and(B[j]==N)): 
   count +=1
#島Xから出る船があるか
#その船の行き先が島Nか

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

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
data = [list(map(int,input().split())) for i in range(M)]
ship = [[] for i in range(2)]
for i in range(M):
    a = data[i][0]
    b = data[i][1]
    if b == N and (a in ship[1])==False:
        ship[1].append(a)
        if a in ship[0]:
            print("POSSIBLE")
            break
    if a == 1 and (b in ship[0])==False:
        ship[0].append(b)   
        if b in ship[1]:
            print("POSSIBLE")
            break
    if i == M-1:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

arr = []
i = 0
for i in range(M):
    t = list(map(int, input().split(" ")))
    arr.append(t)
p1 = [x for x in arr if x[0] == 1]

ii = 0
iii = 0
r = 0
for ii in p1:
    for iii in arr:
        if iii[0] == ii[1]:
            if iii[1] == N:
                r = 1
                break

if (r != 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
e=[]
f=[]
g=0
for i in range(M):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
for j in range(M):
    if b[j]!=N:
        if a[j]!=1:
            pass
        else:
            e.append(b[j])
    else:
        f.append(a[j])
if (len(e)==0) or (len(f)==0):
    print('IMPOSSIBLE')
else:
    for l in range(len(e)):
      if e[l] in f:
        g += 1
        break
      else:
        pass
    if g>0:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

p1 = []
for a in arr:
    if a[0] == 1:
        p1.append(a)

ii = 0
iii = 0
r = 0
for ii in p1:
    for iii in arr:
        if iii[0] == ii[1]:
            if iii[1] == N:
                r = 1
                break

if (r != 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
l = list(map(int, input().split(' ')))
N = l[0]
N_ = l[0] + 1
M = l[1]
y = []
u = []

for i in range(M):
    k = list(map(int, input().split()))
    a = k[0]
    b = k[1]
    if (a == 1):
        y.append(b)
    elif (b == N):
        u.append(a)

for i in y:
    if (i in u):
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
data = [list(map(int,input().split())) for i in range(M)]
ship = [[] for i in range(2)]
for i in range(M):
	a = data[i][0]
	b = data[i][1]
	if b == N and (a in ship[1])==False:
		ship[1].append(a)
	if a == 1 and (b in ship[0])==False:
		ship[0].append(b)
answer = 0
for i in range(len(ship[0])):
	c = ship[0][i]
	if c in ship[1]:
		answer = 1
		break
if answer == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in first:
	if i in second:
		print('POSSIBLE')
		a = 0
		break

if a:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
des = []
first = []
second = []
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		first.append(b[1])
	if b[1] == n:
		second.append(b[0])
###以上1から行ける場所をfirstに格納 終点につながるとこをsecondに格納

for i in first:
	if i in second:
		print('POSSIBLE')
		a = 0
		break

if a:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def main():
    n, m = map(int, raw_input().split())

    l = [map(int, raw_input().split()) for _ in xrange(m)]

    la = []
    lb = []
    for ab in l:
        if ab[0] == 1:
            la.append(ab[1])
        if ab[1] == n:
            lb.append(ab[0])

    for a in la:
        if a in lb:
            print "POSSIBLE"
            return

    print "IMPOSSIBLE"

main()

Submission status: Time Limit Exceeded

Solution code:

nm = input().split(' ')
n = int(nm[0])
m = int(nm [1])
ans  = 'IMPOSSIBLE'

mass = [input().split(' ') for i in range(m)]

for i in mass:
    if '1' in i:
        no1 = 0
        if i[0] == '1' :
            no1 = i[1]
        else:
            no1 = i[0]

        if [str(n) , no1] in mass or [no1, str(n) ]in mass:
            ans  = 'POSSIBLE'
            break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
des = []
first = []
second = []
a = 1
for i in range(0, m):
	des.append(list(map(int, input().split())))
###ここまで入力
###以下出力
for i in des:
	if i[0] == 1:
		first.append(i[1])
	if i[1] == n:
		second.append(i[0])
###以上1から行ける場所をfirstに格納 終点につながるとこをsecondに格納

for i in first:
	if i in second:
		print('POSSIBLE')
		a = 0
		break

if a:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if res:
        break
    if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1) or end[0] == 1, ab_list))) > 0:
        res = True
        break


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
   N,M = map(int,input().split())
   Set = set()
   for i in range(M):
      a,b = map(int,input().split())
      Set.add((a,b))
      Set.add((b,a))                        #ADD
      for j in range(2,N):
         if (1,j) in Set and (j,N) in Set:
            print("POSSIBLE")
            return
   else:
       print("IMPOSSIBLE")

main()

Submission status: Time Limit Exceeded

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

f = []
s = []
for i in range(M):
    a = list(map(int, input().split()))
    if a[0] == 1:
        f.append(a)
    elif a[1] == N:
        s.append(a)
a=0
for i in f:
    for j in s:
        if i[1] == j[0]:
            print("POSSIBLE")
            a=1
if not a:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1) or end[0] == 1, ab_list))) > 0:
        res = True
        break


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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
c=[]
flag=0
for i in range(M):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    if x==1:
        c.append(y)
for i in range(M):
    if b[i]==N:
        if a[i] in c:
            flag+=1
if flag==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
d = {}

def bfs(graph, start, goal): 
#These variables define the visited set (to make sure that the program doesn’t go through the same nodes twice) a queue to make sure that the node seen next is visted first. 
 
    visited, queue = set(), [start] 
    pathsTo = {} 
    pathsTo[start] = [start] 
     
# Ensuring that the queue is not empty at any point in time. 
    while queue: 
# Getting the next node and getting rid of the node in the front of the queue. 
        vertex = queue.pop(0) 
        if vertex not in visited: 
            visited.add(vertex) 
 
 
            # Going through each element in the adjacency list and making sure that it hasn’t been visited, and that it is not in the same path. 
            for newVertex in (graph[vertex]): 
                if newVertex not in visited: 
                    if newVertex not in pathsTo: 
                        pathsTo[newVertex] = list() 
 
                    for path in pathsTo[vertex]: 
                        pathsTo[newVertex].append(str(path)+"->"+str(newVertex)) 
                    queue.append(newVertex) 
    # Return the paths toward the goal.
    if goal not in pathsTo.keys():
        return ["8384793->8->4->7-> 9 8 23748"]
    return pathsTo[goal] 

N, M = map(int,input().split())
for i in range(M):
    a,b = map(int,input().split())
    if a not in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)

    if b not in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)

dist = len(bfs(d,1,N)[0].split("->")) - 1
if dist <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if end[0] == 1:
        res = True
        break

if not res:
    for end in end_list:
        if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1), ab_list))) > 0:
            res = True
            break


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def main():
    n, m = map(int, raw_input().split())

    l = [map(int, raw_input().split()) for _ in xrange(m)]

    la = [ab[0] for ab in l if ab[1] == n]

    for ab in l:
        if ab[0] == 1 and ab[1] in la:
            print "POSSIBLE"
            return

    print "IMPOSSIBLE"

main()

Submission status: Time Limit Exceeded

Solution code:

nm = input().split(' ')
n = int(nm[0])
m = int(nm [1])
ans  = 'IMPOSSIBLE'
mass = []
for i in range(m):
    mass += [input().split(' ' )]

fi = []
se = []
for i in mass:
    if i[0] == '1' or i[1] == '1':
        no1 = 0
        if i[0] == '1' :
            no1 = i[1]
        else:
            no1 = i[0]

        if [str(n) , no1] in mass or [no1, str(n) ]in mass:
            ans  = 'POSSIBLE'
            break


print(ans)

Submission status: Time Limit Exceeded

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

flag = False
for x in a:
    if x in b:
        print('POSSIBLE')
        flag = True
        break
if not flag:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
data = [list(map(int,input().split())) for i in range(M)]
ship = [[] for i in range(N)]
for i in range(M):
	a = data[i][0]
	b = data[i][1]
	if (b in ship[a-1]) == False:
		ship[a-1].append(b)
	if (a in ship[b-1]) == False:
		ship[b-1].append(a)
answer = 0
for i in range(len(ship[0])):
	c = ship[0][i]
	if N in ship[c-1]:
		answer = 1
		break
if answer == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ab_list.sort()

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if end[0] == 1:
        res = True
        break

if not res:
    for end in end_list:
        if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1), ab_list))) > 0:
            res = True
            break


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

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

if any(i in first for i in second):
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ab_list.sort()

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if end[0] == 1:
        res = True
        break

if not res:
    for end in end_list:
        if res:
            break
        for ab in list(filter(lambda x: x[1] == end[0], ab_list)):
            if ab[0] == 1:
                res = True
                break

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

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

for i in second:
	if i in first:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M = map(lambda x: int(x), line.split(" ", 2))

        services_1 = []
        services_n = []
        for i in xrange(M):
            a, b = map(lambda x: int(x), sys.stdin.readline().split(" ", 2))
            if a == 1:
                services_1.append(b)
            if b == N:
                services_n.append(a)

        if 1 in services_n:
            print("POSSIBLE")

        result = "IMPOSSIBLE"
        for service in services_n:
            if service == 1 or service in services_1:
                result = "POSSIBLE"
                break
        print result                

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Here your code !
a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(out)
    elif out==N:
        out2.append(in1)
len_in2=len(in2)
for q in range(len_in2):
    if in2[q] in out2:
        print("POSSIBLE")
        break
    elif q+1==len_in2:
        print("IMPOSSIBLE")
    else:
        continue

Submission status: Time Limit Exceeded

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

ab_list.sort()

start_list = list(filter(lambda x: x[0] == 1, ab_list))

res = False


for start in start_list:
    if start[1] == N:
        res = True
        break
        
if not res:
    for start in start_list:
        if res:
            break
        for ab in list(filter(lambda x: x[0] == start[1], ab_list)):
            if ab[1] == N:
                res = True
                break

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