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:
def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            graph = [[None] * N for _ in range(N)]
            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                graph[a - 1][b - 1], graph[b - 1][a - 1] = 1, 1

            edges_from1 = graph[0].count(1)
            edges_fromN = graph[N - 1].count(1)
            if not edges_from1 or not edges_fromN:
                print("IMPOSSIBLE")
                break

            if edges_fromN < edges_from1:
                start_node = N - 1
                goal_node = 0
            else:
                start_node = 0
                goal_node = N - 1

            for j in range(N):
                if graph[start_node][j] == 1:
                    if graph[j][goal_node] == 1:
                        print("POSSIBLE")
                        raise EndLoop

            print("IMPOSSIBLE")
        except:
            break


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            graph = [[0] * N for _ in range(N)]
            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                graph[a - 1][b - 1], graph[b - 1][a - 1] = 1, 1

            edges_from1 = graph[0].count(1)
            edges_fromN = graph[N - 1].count(1)
            if not edges_from1 or not edges_fromN:
                print("IMPOSSIBLE")
                break

            if edges_from1 < edges_fromN:
                start_node = 0
                goal_node = N - 1
            elif edges_fromN < edges_from1:
                start_node = N - 1
                goal_node = 0
            else:
                start_node = 0
                goal_node = N - 1

            for j in range(N):
                if graph[start_node][j] == 1:
                    if graph[j][goal_node] == 1:
                        print("POSSIBLE")
                        raise EndLoop

            print("IMPOSSIBLE")
        except:
            break


solve()

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"
for i in range(len(list)):
    if list[i][0] == 1:
        for j in range(len(list)):
            if list[i][1] == list[j][0]:
                if list[j][1] == N:
                    ans = "POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N , M = map(int,input().split())
list = [ list(map(int,input().split())) for i in range(M) ]
ans = "IMPOSSIBLE"
for i in range(M):
    if list[i][0] == 1:
        for j in range(M):
            if list[j][1] == N:
                if list[i][1] == list[j][0]:
                    if list[j][1] == N:
                        ans = "POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

N , M = map(int,input().split())
list = [ list(map(int,input().split())) for i in range(M) ]
ans = "IMPOSSIBLE"
for i in range(M):
    if list[i][0] == 1:
        for j in range(M):
            if list[i][1] == list[j][0]:
                if list[j][1] == N:
                    ans = "POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(157):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 157
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 157
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(71):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 71
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 71
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(37):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 37
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 37
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(7):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 7
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 7
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

way_list.sort()
first_list.sort()

for first in first_list:
    if first in way_list:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

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

for first in first_list:
    if first in way_list:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
ship_list = list()
way_list = list()
first_list = list()
for i in range(M):
    a, b = map(int, input().split())
    ship_list.append((a, b))
    if b == N:
        way_list.append(a)
    if a == 1:
        first_list.append(b)

for first in first_list:
    if first in way_list:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
ship_list = list()
way_list = list()
for i in range(M):
    a, b = map(int, input().split())
    ship_list.append((a, b))
    if b == N:
        way_list.append(a)

for dest in ship_list:
    if dest[0] == 1:
        if dest[1] in way_list:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
ship_list = list()
way_list = list()
for i in range(M):
    a, b = map(int, input().split())
    ship_list.append((a, b))
    if b == N:
        way_list.append(a)

for dest in ship_list:
    if dest[1] in way_list and dest[0] == 1:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list_base = [[int(v) for v in input().split(" ")] for v in range(init[1])]  # list(set(map(tuple, )))
pass_one = [v[1] for v in pass_list_base if v[0] == 1]
pass_list = [v for v in pass_list_base if v[0] == target or v[1] == target]
pass_two = sum([len([target for v in pass_list if (v[0] == v2 or v[1] == v2) and (v[0] == target or v[1] == target)]) for v2 in pass_one])

if pass_two > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list_base = [[int(v) for v in input().split(" ")] for v in range(init[1])]  # list(set(map(tuple, )))
pass_list = [v for v in pass_list_base if (v[0] == 1 or v[0] == target) or (v[1] == 1 or v[1] == target)]
pass_one = [v[1] for v in pass_list if v[0] == 1]
pass_two = sum([len([target for v in pass_list if (v[0] == v2 or v[1] == v2) and (v[0] == target or v[1] == target)]) for v2 in pass_one])

if pass_two > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list = list(set(map(tuple, [[int(v) for v in input().split(" ")] for v in range(init[1])])))
pass_one = [v[1] for v in pass_list if v[0] == 1]
pass_two = sum([len([target for v in pass_list if (v[0] == v2 or v[1] == v2) and (v[0] == target or v[1] == target)]) for v2 in pass_one])

if pass_two > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list = [[int(v) for v in input().split(" ")] for v in range(init[1])]
pass_one = [v[1] for v in pass_list if v[0] == 1]
pass_two = sum([len([target for v in pass_list if (v[0] == v2 or v[1] == v2) and (v[0] == target or v[1] == target)]) for v2 in pass_one])
 
if pass_two > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list = [[int(v) for v in input().split(" ")] for v in range(init[1])]
if sum([len([target for v in pass_list if (v[0] == v2 and v[1] == target) or (v[0] == target and v[1] == v2)]) for v2 in [v3[1] for v3 in pass_list if v3[0] == 1]]) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list = [[int(v) for v in input().split(" ")] for v in range(init[1])]
pass_one = [v[1] for v in pass_list if v[0] == 1]
pass_two = sum([len([target for v in pass_list if (v[0] == v2 or v[1] == v2) and (v[0] == target or v[1] == target)]) for v2 in pass_one])

if pass_two > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
init = [int(v) for v in input().split(" ")]
target = init[0]
pass_list = [[int(v) for v in input().split(" ")] for v in range(0, init[1])]
pass_one = [v[0] if v[0] != 1 else v[1] for v in pass_list if v[0] == 1 or v[1] == 1]
pass_two = sum([len([target for v in pass_list if (v[0] == v2 or v[1] == v2) and (v[0] == target or v[1] == target)]) for v2 in pass_one])

if pass_two > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#from collections import defaultdict
from sys import stdin
input = stdin.readline

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

ans = "IMPOSSIBLE"

ls_a,ls_b = [],[]
af,bf = [False]*M,[False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    if a-1 == 0:
        af[m] = True
        ls_a.append(b-1)
    if b-1 == N-1:
        bf[m] = True
        ls_b.append(a-1)
    if af[m] and bf[m]:
        ans = "POSSIBLE"
        break
    
for a in ls_a:
    if ans == "POSSIBLE":
        break
    if a in ls_b:
        ans = "POSSIBLE"
        break

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = "IMPOSSIBLE"

ls = [[] for m in range(M)]
for m in range(M):
    a,b = map(int,(input().split()))
    ls[m].append((a-1,b-1))
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        ls[m].append("P")
    else:
        ls[m].append("I")

for m in range(M):
    if ls[m][1] == "P":
        for i in range(M):
            if ls[m][0][1] == ls[i][0][0] and ls[i][0][1] == N-1:
                ans = "POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"

ls = [[] for m in range(M)]
for m in range(M):
    a,b = map(int,(input().split()))
    ls[m].append(a-1)
    ls[m].append(b-1)
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        ls[m].append("P")
    else:
        ls[m].append("I")

for m in range(M):
    if ls[m][2] == "P":
        for i in range(M):
            if ls[m][1] == ls[i][0] and ls[i][1] == N-1:
                ans = "POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

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

a = []
b = []
c = 0

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


for i in a:
    if i in b:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a = []
b = []
c = 0

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

for i in a:
    if i in b:
        print("POSSIBLE")
        c = 1

if c == 0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = list(filter(lambda x: x<b, c)) + [b] + list(filter(lambda x: x>b, c))
    elif b == N:
        d = list(filter(lambda x: x<a, d)) + [a] + list(filter(lambda x: x>a, d))


j, k = 0, 0
for i in range(1, N):
    if (j > len(c)-1) or (k > len(d)-1):
        print("IMPOSSIBLE")
        break

    if c[j] == d[k]:
        print("POSSIBLE")
        break
    elif c[j] > d[k]:
        k = k+1
    else:
        j = j+1

Submission status: Time Limit Exceeded

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
        c.sort()
    elif b == N:
        d = d + [a]
        d.sort()


j, k = 0, 0
for i in range(1, N):
    if (j > len(c)-1) or (k > len(d)-1):
        print("IMPOSSIBLE")
        break

    if c[j] == d[k]:
        print("POSSIBLE")
        break
    elif c[j] > d[k]:
        k = k+1
    else:
        j = j+1

Submission status: Time Limit Exceeded

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == N:
        d = d + [a]

c.sort()
d.sort()

j, k = 0, 0
for i in range(1, N):
    if (j > len(c)-1) or (k > len(d)-1):
        print("IMPOSSIBLE")
        break

    if c[j] == d[k]:
        print("POSSIBLE")
        break
    elif c[j] > d[k]:
        k = k+1
    else:
        j = j+1

Submission status: Time Limit Exceeded

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == N:
        d = d + [a]

if len(c)<len(d):
    for i in c:
        if i in d:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
else:
    for i in d:
        if i in c:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == N:
        d = d + [a]

for i in c:
    if i in d:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a=[]
b=[]
for i in range(0, M):
    a_tmp, b_tmp = map(int, input().split(" "))
    a = a+[a_tmp]
    b = b+[b_tmp]

c=[]
for i in range(0, M):
    if a[i] == 1:
        c = c + [b[i]]


for i in range(0, M):
    if (a[i] in c) and (b[i] == N):
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

f=0
for x in range(M):
    if A[x]==1:
        if "%s %s" % (B[x], N) in p:
            print("POSSIBLE")
        else:
            f=f+1
    else:
        f=f+1
if f==M:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for x in range(M):
    p.append(input())

f=0
for x in range(1,N+1):
    if "1 %s" % x in p:
        if "%s %s" % (x,N) in p:
            print("POSSIBLE")
        else:
            f=f+1
    else:
        f=f+1
if f==N:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

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

for s in start:
    for f in finish:
        if s == f:
            print 'POSSIBLE'
            exit()

print 'IMPOSSIBLE'

Submission status: Time Limit Exceeded

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

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

for s in start:
    for f in finish:
        if s[1] == f[0]:
            print 'POSSIBLE'
            exit()

print 'IMPOSSIBLE'

Submission status: Time Limit Exceeded

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

N, M = map(int, raw_input().split())
line = []   # 定期便
for i in range(M):
    a, b = map(int, raw_input().split())
    line.append([a, b])
line.sort()

for l in line:
    if l[0] > 1:
        break
    else:
        for k in line:
            if k[0] == l[1] and k[1] == N:
                print 'POSSIBLE'
                exit()

print 'IMPOSSIBLE'

Submission status: Time Limit Exceeded

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

N, M = map(int, raw_input().split())
line = []   # 定期便
for i in range(M):
    a, b = map(int, raw_input().split())
    line.append([a, b])

for l in line:
    if l[0] == 1:
        for k in line:
            if k[0] == l[1] and k[1] == N:
                print 'POSSIBLE'
                exit()

print 'IMPOSSIBLE'

Submission status: Time Limit Exceeded

Solution code:
def Q3(N, M, *arg):
    import numpy as np
    route = np.reshape(np.array(*arg), (M, 2))
    for x in route:
        if x[0] == 1:
            for y in route:
                if x[1] == y[0] and y[1] == N:
                    return 'POSSIBLE'
    return 'IMPOSSIBLE'

N, M = map(int, input().split())
l = [list(map(lambda x: int(x), input().split())) for i in range(M)]
l = [flatten for inner in l for flatten in inner]
print(Q3(N,M,l))

Submission status: Time Limit Exceeded

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

r = False
for a, b in filter(lambda t: t[0] == 1, e):
    if list(filter(lambda t: t[0] == b and t[1] == n, e)):
        r = True
        break
if r:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

import math

N, M = map(int, input().split())
start = []
goal = []
for i in range(M):
    l1, l2 = map(int, input().split())
    if (l1 == 1):
        start.append([l1, l2])
    if (l2 == N):
        goal.append([l1, l2])

def check(st, go):
    for i in st:
        if ([i[1], N] in go):
            return(True)
    return(False)

if (check(start, goal)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

import math

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

def check(l):
    for i in l:
        if (i[0] == '1'):
            for j in l:
                if (j == [i[1], str(N)]):
                    return('POSSIBLE')
    return('IMPOSSIBLE')

print(check(li))

Submission status: Time Limit Exceeded

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

toN =[]
first = []
end = False

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

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

for i in toN:
    if end:
        break
    for j in first:
        if end:
            break
        if i == j:
            print "POSSIBLE"
            end = True
            break


if not end:
    print "IMPOSSIBLE"

Submission status: Time Limit Exceeded

Solution code:
def is_reachable(n, ls, set_1, set_n):
    if n not in set_n:
        return False
    for i in set_1:
        if i in ls:
            return True
    return False
    
n, m = map(int, input().split())
set_1 = set([])
set_n = set([])
ls = []
for i in range(m):
    a, b = map(int, input().split())
    
    if a == 1:
        set_1.add(b)
    if b == n:
        set_n.add(b)
        ls.append(a)
print("POSSIBLE") if is_reachable(n, ls, set_1, set_n) else print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def is_reachable(n, ls, set_1, set_n):
    if n not in set_n:
        return False
    for i in set_1:
        if set((i, n)) in ls:
            return True
    return False
    
n, m = map(int, input().split())
set_1 = set([])
set_n = set([])
ls = []
for i in range(m):
    a, b = map(int, input().split())
    
    if a == 1:
        set_1.add(b)
    if b == n:
        set_n.add(b)
        ls.append(set((a, b)))
print("POSSIBLE") if is_reachable(n, ls, set_1, set_n) else print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def is_reachable(n, ls, set_1, set_n):
    if n not in set_n:
        return False
    for i in set_1:
        if set((i, n)) in ls:
            return True
    return False
    
n, m = map(int, input().split())
set_1 = set([])
set_n = set([])
ls = []
for i in range(m):
    a, b = map(int, input().split())
    
    if a == 1:
        set_1.add(b)
    if b == 1:
        set_1.add(a)
    if a == n:
        set_n.add(a)
        ls.append(set((a, b)))
    if b == n:
        set_n.add(b)
        ls.append(set((a, b)))
print("POSSIBLE") if is_reachable(n, ls, set_1, set_n) else print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def is_reachable(n, ls, set_1, set_n):
    if n not in set_n:
        return False
    for i in set_1:
        if set((i, n)) in ls:
            return True
    return False
    
n, m = map(int, input().split())
set_1 = set([])
set_n = set([])
ls = []
for i in range(m):
    a, b = map(int, input().split())
    ls.append(set((a, b)))
    if a == 1:
        set_1.add(b)
    if b == 1:
        set_1.add(a)
    if a == n:
        set_n.add(a)
    if b == n:
        set_n.add(b)
print("POSSIBLE") if is_reachable(n, ls, set_1, set_n) else print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n_m = raw_input()
n,m = n_m.split()

m = int(m)

shima_1_list = []
shima_2_list = []

i = 0
while i < m:
    teikibin = raw_input()
    teikibin = teikibin.split()
    if teikibin[0] == "1":
        shima_1_list.append(teikibin[1])
    elif teikibin[1] == n:
        shima_2_list.append(teikibin[0])
    i += 1

status = 0

for shima_1 in shima_1_list:
    if shima_1 in shima_2_list:
        status = 1
        break

if status == 0:
    print "IMPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

n_m = raw_input()
n,m = n_m.split()

m = int(m)

shima_1_list = []
shima_2_list = []

i = 0
while i < m:
    teikibin = raw_input()
    teikibin = teikibin.split()
    if teikibin[0] == "1":
        shima_1_list.append(teikibin[1])
    elif teikibin[1] == n:
        shima_2_list.append(teikibin[0])
    i += 1

status = 0

for shima_1 in shima_1_list:
    if shima_1 in shima_2_list:
        status = 1

if status == 0:
    print "IMPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-


n_m = raw_input()
n,m = n_m.split()

n = int(n)
m = int(m)

teikibin = []

i = 0
while i < m:
    teikibin_i = raw_input()
    teikibin_i = teikibin_i.split()
    teikibin.append(teikibin_i)
    i += 1

#print teikibin

shima_1_list = []
shima_2_list = []


i = 0
while i < m:
    if teikibin[i][0] == "1":
        shima_1_list.append(teikibin[i][1])
    elif teikibin[i][1] == str(n):
        shima_2_list.append(teikibin[i][0])
    i += 1

status = 0

for shima_1 in shima_1_list:
    if shima_1 in shima_2_list:
        status = 1

if status == 0:
    print "IMPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Time Limit Exceeded

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-


n_m = raw_input()
n,m = n_m.split()

n = int(n)
m = int(m)

teikibin = []

i = 0
while i < m:
    teikibin_i = raw_input()
    teikibin_i = teikibin_i.split()
    teikibin.append(teikibin_i)
    i += 1

#print teikibin

i = 0
status = 0
while i < m:
    if teikibin[i][0] == "1":
        j = 0
        while j < m:
            if teikibin[j][0] == teikibin[i][1]:
                if teikibin[j][1] == str(n):
                    status = 1
                    break
            j += 1
    i += 1

if status == 0:
    print "IMPOSSIBLE"
else:
    print "POSSIBLE"

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
start = []
end = []
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.append(a*b)
    if a == N or b == N:
        end.append(a * b / N)
flag = 0
for i in start:
    if i in end:
        print("POSSIBLE")
        flag = 1
        break
if not(flag):
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
start = []
end = []
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.append(a*b)
    if a == N or b == N:
        end.append(a * b / N)
flag = 0
for i in start:
    if i in end:
        flag = 1

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
	n, m = map(int, raw_input().split())
	to1 = []
	toN = []

	for i in range(m):
		x, y = map(int, raw_input().split())
		if x == 1:
			to1.append(y)
		if x == n:
			toN.append(y)
		if y == 1:
			to1.append(x)
		if y == n:
			toN.append(x)

	for i in range(n):
		if i in to1 and i in toN:
			print "POSSIBLE"
			return
			
	print "IMPOSSIBLE"

solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
	n, m = map(int, raw_input().split())
	arr = [[0 for i in range(n+1)] for j in range(n+1)]

	for i in range(m):
		x, y = map(int, raw_input().split())
		arr[x][y] = arr[y][x] = 1

	for i in range(n):
		if arr[1][i] == 1 and arr[n][i] == 1:
			print "POSSIBLE"
			return
			
	print "IMPOSSIBLE"

solve()

Submission status: Time Limit Exceeded

Solution code:
import math

def solve(n, m, a, b):
    islands = []

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

    for i in range(m):
        if(a[i] == n and b[i] in islands):
            return "POSSIBLE"
        if(b[i] == n and a[i] in islands):
            return "POSSIBLE"
    return "IMPOSSIBLE"

(n, m) = map(int, input().split())
a = []
b = []

for i in range(m):
    (ai, bi) = map(int, input().split())
    a.append(ai)
    b.append(bi)

print(solve(n, m, a, b))

Submission status: Time Limit Exceeded

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

for i in start:
    if i in end:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
ans="IMPOSSIBLE"
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(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="IMPOSSIBLE"
f=False
for i in range(m):
	if f==False:
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)
		if len(l) != 0:
			for i in l:
				for j in bone:
					if i == j:
						ans="POSSIBLE"
						f=True
	else:a=input()
		
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]
p2 = [x for x in arr if x[1] == N]

ii = 0
iii = 0
r = 0
for ii in p1:
    for iii in p2:
        if iii[0] == ii[1]:
            r = 1
            break
 
if (r != 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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