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())
boat = [list(map(int,input().split())) for _ in range(M)]
flag = 0
for i in range(2,N):
    if [1,i] in boat and [i,N] in boat:
        flag = 1
print("IMPOSSIBLE" if flag == 0 else "POSSIBLE")

Submission status: Time Limit Exceeded

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

g = [[ ] for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    if a == 1 or a == n or b == 1 or b == n:
        bisect.insort(g[a],b)
        bisect.insort(g[b],a)

    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

if len(g[n]) == 0:
    print('IMPOSSIBLE')
    exit()

for i in g[n]:
    if g[i][0] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

g = [[ ] for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    bisect.insort(g[a],b)
    bisect.insort(g[b],a)
    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

if len(g[n]) == 0:
    print('IMPOSSIBLE')
    exit()

for i in g[n]:
    if g[i][0] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[input().split() for _ in range(m)]
ans="IMPOSSIBLE"
for i in range(m):
  if A[i][0]=="1":
    if [A[i][1],str(n)] in A:
      ans="POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

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


arr = []
for x in ab:
    if n in x:
        if x.index(n) == 0:
            arr.append(x[1])
        else:
            arr.append(x[0])

for a, b in ab:
    if a in arr:
        if b == 1:
            print('POSSIBLE')
            exit()
    if b in arr:
        if a == 1:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
# DFS O(N + M)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v: int) -> None:
    for u in G[v]:  # search vertices available from v recursively
        if dist[u] > dist[v] + 1:
            dist[u] = dist[v] + 1
            dfs(u)


def main():
    global G, dist
    N, M = tuple(map(int, input().split()))  # vertices and edges
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    G = [[] for _ in range(N + 1)]  # graph, N+1: 1-idx
    for v, u in E:  # construct a graph according to edges' info
        G[v] += [u]
        G[u] += [v]
    dist = [float("inf")] * (N + 1)  # distance from vertex 1
    dist[1] = 0
    dfs(1)  # search from vertex 1
    flg = dist[-1] <= 2
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
import sys
input = sys.stdin.readline

def dijkstra(s: int) -> int:
    D = [float("inf")] * (N + 1)  # distance
    D[s] = 0
    used = [0] * (N + 1)
    while True:
        v = -1
        for i in range(1, N + 1):
            if not used[i] and (v == -1 or D[i] < D[v]):
                v = i
        if v == -1:
            break
        used[v] = 1
        for j in range(1, N + 1):
            D[j] = min(D[j], D[v] + cost[v][j])
    return D[-1]


def main():
    global N, cost
    N, M = tuple(map(int, input().split()))
    E = tuple(tuple(map(int, input().split())) for _ in range(M))
    # cost[v][u] := cost from vertex v to u
    cost = [[float("inf")] * (N + 1) for _ in range(N + 1)]
    for v, u in E:
        cost[v][u] = 1
        cost[u][v] = 1
    flg = dijkstra(1) <= 2
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]
startship=[]
secondship=[]
for i in range(M):
  if S[i][0]=='1':
    startship.append(S[i])
for v in startship:
  for n in range(M):
    if v[2] == S[n][0] and S[n][2] == str(N):
      print('POSSIBLE')
      exit()    
  
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]

for i in range(M):
  if S[i][0] == '1':
    for n in range(M):
      if S[n][0] =='1':
        pass
      elif S[i][2] == S[n][0] and S[n][2] == str(N):
        print('POSSIBLE')
        exit()
        
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]

for i in range(M):
  if S[i][0] == '1':
    for n in range(M):
      if S[i][2] == S[n][0] and S[n][2] == str(N):
        print('POSSIBLE')
        exit()
        
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"
second_island = []

for a, b in ab_list:
  if a == 1:
    second_island.append(b)

  if b == N:
    if a in second_island:
      ans = "POSSIBLE"
      break

print(ans)

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"
second_island = []

for a, b in ab_list:
  if a == 1:
    second_island.append(b)
    
  if a in second_island:
    if b == N:
      ans = "POSSIBLE"
      break

print(ans)

Submission status: Time Limit Exceeded

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

ans = "IMPOSSIBLE"
second_island = []

for a, b in ab_list:
  if a == 1:
    second_island.append(b)
  
  if a in second_island:
    if b == N:
      ans = "POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

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

A = []
for i in range(M):
  A.append(list(map(int, input().split())))

D1 = [A[i][1] for i in range(M) if A[i][0] == 1]
D2 = [A[i][1] for i in range(M) if A[i][0] in D1]
if N in D2:
  print ("POSSIBLE")
else:
  print ("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

A = []
B = []
for i in range(M):
  a, b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

flag = False
if 1 not in A:
  print ("IMPOSSIBLE")
else:
  for i in range(M):
    if A[i] == 1:
      for j in range(M):
        if A[j] == B[i] and B[j] == N:
          print ("POSSIBLE")
          flag =True
  if not flag:
    print ("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
B=[list(map(int,input().split())) for _ in range(M)]
li=[]
ans="IMPOSSIBLE"
for i,j in B:
  if i==1:
    li.append(j)
for l in li:
  if l==N:
    ans="POSSIBLE"
  else:
    for i,j in B:
      if i==l and j==N:
        ans="POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N, M = map(int, input().split())
AB = [tuple(sorted(map(int, input().split(' ')))) for _ in range(M)]

ans = 0
for i in range(2, N):
    if tuple([1, i]) in AB and tuple([i, N]) in AB:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import itertools


N, M = map(int, input().split())
AB = [tuple(sorted(map(int, input().split(' ')))) for _ in range(M)]

ans = 0
for i in range(2, N):
    l = [1, i, N]
    ans += sum([1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in AB]) == 2
if ans > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

start = []
goal = []
flag = False

for i in range(m):
    if 1 in a[i]:
        start.append(a[i])
    if n in a[i]:
        goal.append(a[i])

for i in range(len(goal)):
    middle_i = goal[i][0]
    for j in range(len(start)):
        if start[j][1] == middle_i:
            flag = True
            break
    else:
        continue
    break

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

Submission status: Time Limit Exceeded

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

for i in s[1]:
    for j in e[N]:
        if i == j:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools

YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(M):
        G[a[i]-1].append(b[i]-1)
        G[b[i]-1].append(a[i]-1)
    flag = False
    for g in G[0]:
        if g in G[-1]:
            flag = True
    if flag:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
X, Y = [],[]
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        X.append(B)
    elif B == N:
        Y.append(A)

for i in X:
    for j in Y:
        if i == j:
            print("POSSIBLE")
            exit(0)
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in range(M):
    if a[i] == 1:
        A.append(a[i])
        B.append(b[i])
    elif b[i] == N:
        X.append(a[i])
        Y.append(b[i])

for i in range(len(X)):
    for j in range(len(A)): # 1
        if X[i] == B[j]: # N
            print("POSSIBLE")
            exit(0)
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def main(N,M,to_,from_):
    ans = "IMPOSSIBLE"
    
    for to in to_:
        if to in from_:
            ans = "POSSIBLE"
            break
            
    print(ans)

if __name__ == '__main__':
    N, M = map(int, input().split())
    to_, from_ = [], []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1):
            to_.append(b)
        elif(b==N):
            from_.append(a)
    main(N,M,to_,from_)

Submission status: Time Limit Exceeded

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

def main(N,M,islands):
    queue = []
    flag = False
    for a,b in islands:
        if(a==1):
            queue.append(b)
    for a,b in islands:
        if(a in queue and b==N):
            flag = True
            break
            
    print("POSSIBLE") if flag else print("IMPOSSIBLE")

if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1 or b==N):
            islands.append([a,b])
    main(N,M,islands)

Submission status: Time Limit Exceeded

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

def main(N,M,islands):
    queue = []
    flag = False
    islands_s = sorted(islands, key=lambda x: x[0])
    islands_t = sorted(islands, key=lambda x: x[1], reverse=True)
    for a,b in islands_s:
        if(a==1):
            queue.append(b)
        else:
            break
    for a,b in islands_t:
        if(b!=N):
            break
        elif(a in queue and b==N):
            flag = True
            
    print("POSSIBLE") if flag else print("IMPOSSIBLE")

if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1 or b==N):
            islands.append([a,b])
    main(N,M,islands)

Submission status: Time Limit Exceeded

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

def main(N,M,islands):
    queue = []
    flag = False
    islands_s = sorted(islands, key=lambda x: x[0])
    for a,b in islands:
        if(a==1):
            queue.append(b)
    for a,b in islands:
        if(a in queue and b==N):
            flag = True
    print("POSSIBLE") if flag else print("IMPOSSIBLE")

if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    for i in range(M):
        a, b = map(int, input().split())
        islands.append([a,b])
    main(N,M,islands)

Submission status: Time Limit Exceeded

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

ab = []

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

for i in ab:
    if i[0] == 0:
        next_p = i[1]
        for j in ab:
            if j[0] == next_p:
                if j[1] == n:
                    print("POSSIBLE")
                    exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
L=[list(map(int,input().split())) for _ in [0]*m]
for l in L:
    if l[0]==1:
        if [l[1],n] in L: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 _ in [0]*m]
for i in range(2,n):
    if [1,i] in l and [i,n] in l: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 _ in [0]*m]
if all([1,i] not in l or [i,n] not in l for i in range(2,n)):print('IM',end='')
print('POSSIBLE')

Submission status: Time Limit Exceeded

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

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

while (4 not in visited) and H:
  x = H.popleft()
  for y in ship[x]:
    if visited[y] == 0:
      H.append(y)
      visited[y] = visited[x] + 1
if 0 < visited[N-1] < 4:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
onetox=set()
xtoN=set()
ans="IMPOSSIBLE"
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        onetox=onetox | {b}
    if b==N:
        xtoN=xtoN | {a}
    if len(onetox & xtoN)>0:
        ans="POSSIBLE"
print(ans)

Submission status: Time Limit Exceeded

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

ans="IMPOSSIBLE"
for i in onetox:
    if i in xtoN:
        ans="POSSIBLE"
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
start = []
to_goal = []
for i in range(M):
    s = input().split()
    if int(s[0])==1:
        start.append(int(s[1]))
    elif int(s[1]) == N:
        to_goal.append(int(s[0]))
flag = 0
for i in range(len(start)):
    for j in range(len(to_goal)):
        if start[i] == to_goal[j]:
            flag = 1
            break
    if flag == 1:
        break
        
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

ab = [list(map(int,input().split())) for _ in range(m)]
s = [ab[i][1] for i in range(m) if ab[i][0] == 1]
g = [ab[i][0] for i in range(m) if ab[i][1] == n]
f = 0
s.sort()
s.reverse()
g.sort()
for i in s:
    if i in g:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

ab = [list(map(int,input().split())) for _ in range(m)]
s = [ab[i][1] for i in range(m) if ab[i][0] == 1]
g = [ab[i][0] for i in range(m) if ab[i][1] == n]
f = 0
for i in s:
    if i in g:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

s = []
g = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    if b == n:
        g.append(a)
f = 0
s = list(set(s))
g = list(set(g))
for i in range(len(s)):
    if s[i] in g:
        f = 1
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

s = []
g = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    if b == n:
        g.append(a)
f = 0
for i in range(len(s)):
    if s[i] in g:
        f = 1
if f:
    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)]

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

for i in range(m):
    if ab[i][0] in ninoshima and ab[i][1]==n:
        print("POSSIBLE")
        quit()
    elif ab[i][1] in ninoshima and ab[i][0]==n:
        print("POSSIBLE")
        quit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:

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

slink = []
glink = []

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink.append(b)
    elif b == 1:
        slink.append(a)
    elif a == N:
        glink.append(b)
    elif b == N:
        glink.append(a)

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

print (ans)

Submission status: Time Limit Exceeded

Solution code:

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

slink = []
glink = []

for i in range(M):

    a,b = map(int,input().split())

    if a == 1:
        slink.append(b)
    elif b == 1:
        slink.append(a)
    elif a == N:
        glink.append(b)
    elif b == N:
        glink.append(a)

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"

print (ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for j in range(m)]
a.sort(key=lambda x:x[1])
a.sort(key=lambda x:x[0])
cc=0
for i in range(m):
    if a[i][0]==1:
        for j in range(m):
            if a[i][1]==a[j][0] and a[j][1]==n:
                cc=1
print("POSSIBLE" if cc==1 else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))
atob = []
btoz = []
for _ in range(M):
    a, b = list(map(int,input().split()))
    if a == 1:
        if b in btoz:
            print('POSSIBLE')
            break
        atob.append(b)
    elif b == N:
        if a in atob:
            print('POSSIBLE')
            break
        btoz.append(a)
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)]

for a, b in ab:
    if a == 1:
        for a2, b2 in ab:
            if a2 == b and b2 == n:
                print("POSSIBLE")
                exit()
    if b == 1:
        for a2, b2 in ab:
            if b2 == a and a2 == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
port=[]
ans="IMPOSSIBLE"
for i in range(m):
    a=list(map(int,input().split()))
    port+=[a]
anslist=[]
for i in range(m):
    if port[i][1]==n:
        anslist+=[port[i][0]]
for i in range(m):
    for u in range(0,len(anslist)):
        if port[i][1]==anslist[u] and port[i][0]==1:
            ans="POSSIBLE"
            break
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
if m == 1:
    print("IMPOSSIBLE")
    exit()
a = []
for i in range(m):
    arr = list(map(int,input().split()))
    a.append(arr)
l = [i[1] for i in a if i[0]==1]
for i in l:
    l_2 = [j[1] for j in a if j[0]==i]
    if n in l_2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
IN,OUT,p=[],[],0
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:IN.append(b)
    if b==n:OUT.append(a)
for i in IN:
    if i in OUT:p=1
if p==1:print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [[0, 0] for _ in range(M)]
one = []
ans = "IMPOSSIBLE"

for i in range(M):
    ab[i] = [int(ele) for ele in input().split()]


def main():
    # 1 hop
    global ab
    for i in range(M):
        if ab[i][0] == 1:
            one.append(ab[i][1])
            if ab[i][1] == N:
                print("POSSIBLE")
                exit()
    # 2 hop
    ab = list(filter(lambda x: x[0] in one and x[1] == N, ab))
    print("IMPOSSIBLE" if len(ab) == 0 else "POSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [0] * M
b = [0] * M
one = []
ans = "IMPOSSIBLE"

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


def main():
    # 1 hop
    for i in range(M):
        if a[i] == 1:
            one.append(b[i])
            if b[i] == N:
                print("POSSIBLE")
                exit()

    for i in range(M):
        if a[i] in one and b[i] == N:
            print("POSSIBLE")
            exit()

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

A = []
B = []
buff = [0 for i in range(N+1)]
buff2 = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        # buff[b] = 1
        buff[b] = 1
    if b == N:
        B.append(a)
        buff2[a] = 1

# print(buff)
# print(buff2)

seikai1 = []
for i in range(N+1):
    if buff[i] == 1:
        seikai1.append(i)

for i in range(N+1):
    if buff2[i] == 1:
        if i in seikai1:
            print('POSSIBLE')
            exit()
# for i in range(len(buff)):
#     for j in range(len(buff2)):
#         if buff[i] == 1 and buff2[j] == 1:
#             print('POSSIBLE')
#             exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

A = []
B = []
buff = [0 for i in range(M+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        # buff[b] = 1
    if b == N:
        B.append(a)

# print(A)
# print(B)
for i in range(len(A)):
    for j in range(len(B)):
        if A[i] == B[j]:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dat_m = [[]] * (n+1)
dat_finish = [False] * (n+1)


for i in range(m):
    a,b = map(int, input().split())
    dat_m[a] = dat_m[a] + [b]
    if b == n:
        dat_finish[a] = True
#print(dat_m)
#print(dat_finish)

c = False
for i in dat_m[1]:
    if dat_finish[i]:
        c = True
print("POSSIBLE" if c else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dat_m = [[]] * (n+1)
for i in range(m):
    a,b = map(int, input().split())
    dat_m[a] = dat_m[a] + [b]
# print(dat_m)

c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True
print("POSSIBLE" if c else "IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,m =map(int,input().split())
a = []
b = []
for i in range(m):
    aa, bb = map(int,input().split())
    a.append(aa)
    b.append(bb)
cnt = 0

for i in range(2,n):
    for j in range(m):
        if a[j] == 1 and b[j] == i:
            for l in range(m):
                if a[l] == b[j] and b[l] == n:
                    cnt = 1
                    break
            break
    if cnt == 1:
        break

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
flag=False
one = []
enu = []
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    one.append(b)
  elif b==n:
    enu.append(a)

for i in one:
  if i in enu:
    flag=True
    break

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
flag=False
one = []
enu = []
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    one.append(b)
  elif b==n:
    enu.append(a)

for i in one:
  if i in enu:
    flag=True

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

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m = map(int,input().split())

li1 = []
li2 = []

for i in range(m):
    s = list(input().split())
    if "1" in s:
        li1.append(s)
    elif str(n) in s:
        li2.append(s)
        
for i in range(len(li1)):
    for j in range(len(li2)):
        x = set(li1[i]) | set(li2[j])
        if len(x) == 3:
            print("POSSIBLE")
            sys.exit()
    

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m = map(int,input().split())

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

for i in range(m-1):
    for j in range(i+1,m):
        s = set(li[i]) | set(li[j])
        if 1 in s and n in s and len(s) == 3:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[set(map(int,input().split())) for _ in range(m)]
S=set()
G=set()
for x in l:
	if 1 in x:S=S|x
	elif n in x:G=G|x
print('POSSIBLE' if len(S&G)>0 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)]

to_i = [0]*(n-2)
to_n = [0]*(n-2)

for i in range(2,n):
    if [1,i] in l:
        to_i[i-2] = 1
    
    if [i,n] in l:
        to_n[i-2] = 1

c = 0
    
for i in range(n-2):
    if c == 1:
        break
    if to_i[i] == 1 and to_n[i] == 1:
        c += 1

if c == 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 _ in range(M)]


import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False
cnt = 0
ab2 = [[0]] * (N+1)
for j in range(M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
for i in ab2[1][1:]:
    q.put(i)
    cnt += 1
idx = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if idx < cnt:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    idx += 1
print('IMPOSSIBLE')