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())
c = []
d = []
for i in range(m): 
  r = list(map(int,input().split()))
  if r[0] == 1 or r[1] == n:
    c.append(r)
    if r[1] == n:
      d.append(r[0])
ans = [z for z in c if z[0] == 1 and z[1] in d ]
print('IMPOSSIBLE' if len(ans) == 0 else 'POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]
c = [x for x in a if x[0] == 1 or x[1] == n]
d = [z[0] for z in c if z[1] == n ]
ans = [z for z in c if z[0] == 1 and z[1] in d ]
print('IMPOSSIBLE' if len(ans) == 0 else 'POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
k=[]
l=[]
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k.append(tb)
    if tb == H:
        l.append(ta)
s = 0
for i in range(len(k)):
    for j in range(len(l)):
        if k[i] == l[j]:
            s = 1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
k=[]
l=[]
def intersection(lst1, lst2): 
    lst3 = [value for value in lst1 if value in lst2] 
    return lst3 
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k.append(tb)
    if tb == H:
        l.append(ta)
s = 0
p = intersection(l,k)
if len(p)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
H, W = map(int, input().split())
k=[]
l=[]
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k.append(tb)
    if tb == H:
        l.append(ta)
s = 0
for i in range(len(k)):
    for j in range(len(l)):
        if k[i] == l[j]:
            s = 1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
nl = [[] for i in range(n+1)]
for a,b in s: nl[a].append(b);nl[b].append(a)
ans = "IMPOSSIBLE"
for i in range(2,n):
    if i in nl[1] and i in nl[n]: ans = "POSSIBLE" 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]


from collections import defaultdict, Counter
import math
from bisect import bisect_left, bisect_right
import numpy as np

#### START
n, m= map(int,input().split())
one_fune = []
n_fune = []
for _ in range(m):
    li = list(map(int,input().split()))
    if 1 in li:
        li.remove(1)
        one_fune.append(li[0])
    elif n in li:
        li.remove(n)
        n_fune.append(li[0])

flag = False
for o in one_fune:
    if o in n_fune:
        flag = True
        break

if flag:
    print("POSSIBLE")
else:
    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)]
flag = 0
for i in range(M):
    if ab[i][0] == 1:
        j = 0
        for j in range(M):
            if ab[j] == [ab[i][1],N]:
                print("POSSIBLE")
                flag = 1
                break
    if flag == 1:
        break
if flag == 0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in range(m):
    if a[i][0] == "1":
        A.add(a[i][1])
    if a[i][1] == str(n):
        B.add(a[i][0])
    if A & B:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
AB = [[int(i) for i in input().split()] for i in range(m)]
S = []
G = []

for ab in AB:
    if ab[0] == 1:
        S.append(ab)
    if ab[1] == n:
        G.append(ab)
        
ans = 'IMPOSSIBLE'
for s in S:
    for g in G:
        if s[1] == g[0]:
            ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
onelist,nlist = [],[]
for i in range(M):
    aa,bb = map(int,input().split())
    if aa == 1:
        onelist.append(bb)
    if bb == N:
        nlist.append(aa)

for b in onelist:
    if b in nlist:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#068-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
import numpy as np
n,m=IL()
nm=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b=IL()
    nm[a-1][b-1]=1
    nm[b-1][a-1]=1
nm=np.array(nm)
nm=nm.dot(nm)
if nm[0][n-1]==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
fir = []
sec = []

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fir.append(b)
    elif a == n:
        sec.append(b)
    if b == 1:
        fir.append(a)
    elif b == n:
        sec.append(a)

for i in fir:
    if i in sec:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a=[]
b=[]
l=[]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if a[i]==1 or b[i]==1:
        l.append(a[i]*b[i])


for i in range(m):
    if b[i]==n:
        if a[i] in l:
            print("POSSIBLE")        
            sys.exit()
    if a[i]==n:
        if b[i] in l:
            print("POSSIBLE")
            sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a=[]
b=[]
l=[]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if a[i]==1 or b[i]==1:
        l.append(a[i]*b[i])


for i in range(m):
    if a[i] in l and b[i]==n:
        print("POSSIBLE")
        sys.exit()
    if b[i] in l and a[i]==n:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

a=[]
b=[]

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

l=[]

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

for i in range(m):
    if a[i] in l and b[i]==n:
        print("POSSIBLE")
        sys.exit()
    if b[i] in l and a[i]==n:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(tuple(map(int,input().split())))

from1 = []
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.append(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(list(map(int,input().split())))

from1 = []
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.append(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = [0 for _ in range(N+1)]
stack = [[N,0]]
count[N] = 1
ok = False
for i in range(2*M):
    if stack == []:
        break
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                if count[i] == 0:
                    stack.append([i,arr[1]+1])
                    count[i] = 1
print('POSSIBLE' if ok else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = 0
stack = [[N,0]]
ok = False
for i in range(2*M):
    if stack == []:
        break
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                stack.append([i,arr[1]+1])
print('POSSIBLE' if ok else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
edge = [[] for _ in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go].append(to)
    edge[to].append(go)
count = 0
stack = [[N,0]]
ok = False
while(stack != []):
    arr = stack.pop(0)
    if arr[1] < 3:
        if arr[0] == 1:
            ok = True
            break
        else:
            for i in edge[arr[0]]:
                stack.append([i,arr[1]+1])
print('POSSIBLE' if ok else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
def abc068_c():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    first_candidate = []
    second_candidate = []
    for i in range(m):
        if ab[i][0] == 1:
            first_candidate.append(ab[i][1])
        elif ab[i][1] == n:
            second_candidate.append(ab[i][0])
    for v in first_candidate:
        if v in second_candidate:
            print("POSSIBLE")
            return None
    print("IMPOSSIBLE")


abc068_c()

Submission status: Time Limit Exceeded

Solution code:
def abc068_c():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    first_index = []
    for i in range(m):
        if ab[i][0] == 1:
            first_index.append(ab[i][1])

    for i in range(m):
        if ab[i][0] in first_index and ab[i][1] == n:
            print("POSSIBLE")
            return 0
    print("IMPOSSIBLE")


abc068_c()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
c=0
for j in range(n):
  if [j,1] in l or [1,j] in l:
    if [j,n] in l or [n,j] in l:
      c+=1
      break
if c==1:print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
L=[]
for j in range(m):
  if l[j][0]==1:L.append(l[j][1])
  if l[j][1]==1:L.append(l[j][0])
c=0
for k in range(len(L)):
  if c!=0:
    break
  for j in range(m):
    if L[k]==l[j][0] and l[j][1]==n:
      c+=1
      break
    if L[k]==l[j][1] and l[j][0]==n:
      c+=1
      break
if c==1:print('POSSIBLE')
else:print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

edge = []

for m in range(M):
    a, b = map(int, input().strip().split(" "))
    if (a == 1 or a == N) or (b == 1 or b == N):
        edge.append((a, b))

res = False
for n in range(N):
    if len([e for e in edge if e[0] == 1 and e[1] == n]) > 0 and len([e for e in edge if e[0] == n and e[1] == N]) > 0:
        print("POSSIBLE")
        res = True
        break


if not res:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

edge = []

for m in range(M):
    a, b = map(int, input().strip().split(" "))
    edge.append((a,b))

to_one = [False] * N
to_N = [False] * N

for n in range(N):
     to_one[n] = len([e for e in edge if e[0] == 1 and e[1] == n]) > 0
     to_N[n] = len([e for e in edge if e[0] == n and e[1] == N]) > 0

res = False
for n in range(N):
    if to_one[n] and to_N[n]:
        print("POSSIBLE")
        res = True
        break

if not res:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

edge = []

for m in range(M):
    a, b = map(int, input().strip().split(" "))
    edge.append((a,b))

one_step = [e[1] for e in edge if e[0] == 1]

pos = False
for i, o in enumerate(one_step):
    pos = len([x for x in edge if  x[0] == o and x[1] == N]) > 0
    if pos:
        break

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

Submission status: Time Limit Exceeded

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

edge = []

for m in range(M):
    a, b = map(int, input().strip().split(" "))
    edge.append((a,b))

one_step = []
for i, e in enumerate(edge):
    if e[0] == 1:
        one_step.append(e[1])

pos = False
for i, o in enumerate(one_step):
    for e in filter(lambda x: x[0] == o, edge):
        if e[1] == N:
            print("POSSIBLE")
            pos = True

if not pos:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
candi_a = []
candi_b = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        candi_a.append(b)
    elif b == n:
        candi_b.append(a)
count = 0
for i in candi_a:
    if i in candi_b:
        print("POSSIBLE")
    else:
        count += 1
if count == len(candi_a):
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
l,B_s,B_l = [],[],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        if b < N:
            B_s.append(b)
        elif b > N:
            B_l.append(b)        
    l.append([a,b])
for e in l:
    if e[0] in B_s and e[1] == N:
        print("POSSIBLE")
        break
    elif e[1] in B_l and e[0] == N:
        print("POSSIBLE")
        break
    elif e == l[-1]:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
l,B = [],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        B.append(b)
    l.append([a,b])
for e in l:
    if e[0] in B and e[1] == N:
        print("POSSIBLE")
        break
    elif e[1] in B and e[0] == N:
        print()("POSSIBLE")
        break
    elif e == l[-1]:
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
#print(n,m,l)
def bin_search(a,li):
    max_len=len(li)
    min_len=0
    while max_len>min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif abs(min_len-max_len)==1 and min_len>=0 and li[min_len]!=a and max_len<len(li) and li[max_len]!=a:
            break
        elif li[mid]<a:
            min_len=mid
        else:
            max_len=mid
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

hune1 = []
hune2 = []
for keiro in hunes:
  keiro.sort()
  if keiro[0] == 1:
    hune1.append(keiro)
  if keiro[1] == n:
    hune2.append(keiro)

count = 0
for i in hune1:
  for j in hune2:
    if i[1] == j[0]:
      print("POSSIBLE")
      count += 1
if count == 0:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

hune1 = []
hune2 = []
for keiro in hunes:
  keiro.sort()
  if keiro[0] == 1:
    hune1.append(keiro)
  if keiro[1] == n:
    hune2.append(keiro)

tohune1 = []
for to in hune1:
  tohune1.append(to[1])

fromhune2 = []
for fom in hune2:
  fromhune2.append(fom[0])

ikeru = []
for to in tohune1:
  for fom in fromhune2:
    if to == fom:
      print("POSSIBLE")
      ikeru.append(1)
if len(ikeru) == 0:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
a = [None for i in range(2 * M)]
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a[2*i] = [A, B]
    a[2*i+1] = [B, A]

a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break

for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")
            break

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
a = [None for i in range(2 * M)]
number = [None for i in range(2 * M)]
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a[2*i] = [A, B]
    a[2*i+1] = [B, A]
    number[2*i]
    number[2*i+1]
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break
def intersect_list(lst1, lst2):
    arr = []
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            pass
        else:
            arr.append(element)
    return arr
if len(intersect_list(one, two)) != 0:
    print("POSSIBLE")

else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break
def intersect_list(lst1, lst2):
    arr = []
    lst = lst1.copy()
    for element in lst2:
        try:
            lst.remove(element)
        except ValueError:
            pass
        else:
            arr.append(element)
    return arr
if len(intersect_list(one, two)) != 0:
    print("POSSIBLE")

else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

for i in range(M):
    if b[i][0] == N:
        two.append(b[i][1])
    else:
        break

for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")
            break
    if flag == 1:
        break

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
b = a[:]
b.reverse()
one = []
two = []
for i in range(M):
    if a[i][0] == 1:
        one.append(a[i][1])
    else:
        break

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

for i in range(len(one)):
    for j in range(len(two)):
        if one[i] == two[j]:
            flag = 1
            print("POSSIBLE")
            break
    if flag == 1:
        break

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
a = []
number = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append([A, B])
    a.append([B, A])
    number.append(A)
    number.append(B)
a.sort()
number.sort()
for i in range(bisect.bisect_right(number, 1)):
    for j in range(2*M):
        if a[i][1] == a[j][0] and a[j][1] == N:
            print("POSSIBLE")
            flag = 1
            break
    if flag == 1:
        break

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = []
b = []
flag = 0
for i in range(M):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)
    a.append(B)
    b.append(A)
for i in range(2*M):
    if a[i] == 1:
        for j in range(2*M):
            if b[i] == a[j] and b[j] == N:
                print("POSSIBLE")
                flag = 1
                break
    if flag == 1:
        break

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

Submission status: Time Limit Exceeded

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

st = []
tt = []

for i in range(M):
    s, t = list(map(int, input().rstrip().split()))
    if s == 1:
        st.append(t)
    
    if t == N:
        tt.append(s)

st.sort()
tt.sort()
result = 'IMPOSSIBLE'
for s in st:
    if s in tt:
        result = 'POSSIBLE'
        break


print(result)

Submission status: Time Limit Exceeded

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

st = []
tt = []

for i in range(M):
    s, t = list(map(int, input().rstrip().split()))
    if s == 1:
        st.append(t)
    
    if t == N:
        tt.append(s)

result = 'IMPOSSIBLE'
for s in st:
    if s in tt:
        result = 'POSSIBLE'
        break


print(result)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
a, b, d = [0]*M, [0]*M, [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    a[i], b[i] = a[i] - 1, b[i] - 1

G = csr_matrix(([1]*M, (a, b)), shape=(N, N))
D = dijkstra(G, directed=False, indices=[0, N-1])
if D[0][N-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:


import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    d1 = set()
    dN = set()
    for _ in range(iM):
        a,b = [int(_) for _ in sys.stdin.readline().split()]
        if a == 1 :
            d1.add(b)
        if b == iN:
            dN.add(a)
        if d1 & dN :
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")
解()

Submission status: Time Limit Exceeded

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

ans = 'IMPOSSIBLE'
for i in range(M):
	if l[i][0] == 1:
		t = l[i][1]
		for j in range(M):
			if l[j][0] == t and l[j][1] == N:
				ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
for i in range(len(f_1)):
    for j in range(len(t_n)):
        if f_1[i] == t_n[j]:
            jedge = 1
            break
    if jedge == 1:
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

AB = sorted(AB)

first = []
for a,b in AB:
    if a == 1:
        first.append(b)
    else:
        break

AB = sorted(AB, key=lambda x:x[1], reverse=True)
sec = []
for a,b in AB:
    if b == N:
        sec.append(a)
    else:
        break

for f in first:
    if f in sec:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
for x in p:
  if x in q:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
L1=[]
LN=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        if b in LN:
            print("POSSIBLE")
            exit()
        else:
            L1.append(b)
    elif b==N:
        if a in L1:
            print("POSSIBLE")
            exit()
        else:
            LN.append(a)
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

index = 0
while index < m:
    listI = list(map(int, input().split()))
    if listI[0] == 1:
        oneToL.append(listI[1])
    elif listI[1] == n:
        toNL.append(listI[0])
    index += 1

if len(toNL) < len(oneToL):
    index2 = 0
    while index2 < len(toNL):
        if toNL[index2] in oneToL:
            print("POSSIBLE")
            break
        else:
            index2 += 1

    if index2 == len(toNL):
        print("IMPOSSIBLE")
else:
    index2 = 0
    while index2 < len(oneToL):
        if oneToL[index2] in toNL:
            print("POSSIBLE")
            break
        else:
            index2 += 1

    if index2 == len(toNL):
        print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

index=0
flag = 0
while index < m:
    listI = list(map(int, input().split()))
    if listI[0] == 1:
        if listI[1] in oneToL:
            pass
        else:
            oneToL.append(listI[1])
        if listI[1] in toNL:
            flag =1
    elif listI[1] == n:
        if listI[0] in toNL:
            pass
        else:
            toNL.append(listI[0])
        if listI[0] in oneToL:
            flag = 1
    index+=1

if flag ==1:
    print("POSSIBLE")
else:
    if len(toNL) < len(oneToL):
        index2=0
        while index2 < len(toNL):
            if toNL[index2] in oneToL:
                print("POSSIBLE")
                break
            else:
                index2+=1

        if index2 == len(toNL):
            print("IMPOSSIBLE")
    else:
        index2 = 0
        while index2 < len(oneToL):
            if oneToL[index2] in toNL:
                print("POSSIBLE")
                break
            else:
                index2 += 1

        if index2 == len(toNL):
            print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

index=0
while index < m:
    listI = list(map(int, input().split()))
    if listI[0] == 1:
        oneToL.append(listI[1])
    elif listI[1] == n:
        toNL.append(listI[0])
    index+=1

index2=0
while index2 < len(toNL):
    if toNL[index2] in oneToL:
        print("POSSIBLE")
        break
    else:
        index2+=1

if index2 == len(toNL):
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

ch = 0
if N in B and 1 in A:
    AA = []
    BB = []
    for i in range(M):
        if A[i] == 1:
            AA.append(B[i])
        if B[i] == N:
            BB.append(A[i])
else:
    print('IMPOSSIBLE')
    exit()


for b in AA:
    if b in BB:
        ch = 1
if ch == 1:
    print('POSSIBLE')
else:
    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)]
ans = 0
tyukan = []
saigo = []
 
for i in range(M):
    if ab[i][0] == 1:
        tyukan.append(ab[i][1])
 
for i in range(M):
    if ab[i][0] in tyukan:
        if ab[i][1] == N:
            ans =1
            break
 
print('POSSIBLE' if ans == 1 else 'IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
flag = False
j = 0
while (0 <= j <= len(L)-1):
  k = L[j][1]
  if ([1,k] in L):
    if ([k,N] in L):
      flag = True
      break
    else:
      j += 1
  else:
    j += 1
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
line = []
 
for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)
 
start = 1
end = N
second = []
 
for l in line:
    if l[0] == start:
        second.append(l[1])
    elif l[1] == start:
        second.append(l[0])
 
for l in line:
    if l[0] in second:
        if l[1] == end:
            print('POSSIBLE')
            exit()
    if l[1] in second:
        if l[0] == end:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')