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: Accepted

Solution code:
n, m = map(int, input().split())
s, e = set(), set()
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.add(b)
    elif b == n:
        e.add(a)
if len(s & e) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
m = set()
m2 = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        m.add(b)
    if b == N:
        m2.add(a)
for me in m:
    if me in m2:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# coding: utf-8
from queue import Queue

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

graph = [ [] for i in range(N+1)]
for i in range(M):
    a, b = tuple(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

def is_reach(n):
    dist = [0 for i in range(N+1)]
    is_visit = [False for i in range(N+1)]
    is_visit[1] = True
    q = Queue()
    q.put(1)
    while not q.empty():
        v = q.get()
        for u in graph[v]:
            if not is_visit[u]:
                is_visit[u] = True
                q.put(u)
                dist[u] = dist[v] + 1
                if u == n and dist[u] == 2:
                    return True
                if dist[u] > 2:
                    return False
    return False

print("POSSIBLE" if is_reach(N) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
#Cat Snuke and a Voyage

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

l = [[] for i in range(N)]
for pi in p:  #0-originedに注意
    l[pi[0]-1].append(pi[1])
    l[pi[1]-1].append(pi[0])

flag = False

for li in l[0]:
    if( N in l[li-1] ):
        flag = True
        break

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

Submission status: Accepted

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

for _ in range(M):
    a, b = list(map(int, input().split()))

    if a == 1:
        dest_list_1.append(b)
    elif b == 1:
        dest_list_1.append(a)
    elif a == N:
        dest_list_2.append(b)
    elif b == N:
        dest_list_2.append(a)

len_dest_1 = len(dest_list_1)
len_dest_2 = len(dest_list_2)

if len(set(dest_list_1 + dest_list_2)) == len_dest_1 + len_dest_2:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

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

head = [-1 for _ in range(N + 1)]
edge= [-1 for _ in range(M + 1)]
next = [-1 for _ in range(M + 1)]

tot = 0

def add_edge(a, b):
  global tot
  edge[tot] = b
  next[tot] = head[a]
  head[a] = tot
  tot += 1

for _ in range(M):
  a, b = map(int, input().strip().split(" "))
  add_edge(a, b)

def find(start, step):
  if step == 0:
    if start == N:
      return True
    else:
      return False
  p = head[start]
  while p != -1:
    if find(edge[p], step - 1) == True:
      return True
    p = next[p]
  return False

if find(1, 2) == True:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [[0 for i in range(2)] for j in range(M)]
s = set()
ispossible = False
for i in range(M):
	ab[i] = list(map(int, input().split()))
	if ab[i][0] == 1:
		s.add(ab[i][1])
for i in range(M):
	if ab[i][0] in s and ab[i][1] == N:
		ispossible = True
		break
if ispossible:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
S1 = []
S2 = []
for i in range(M):
	S1 = [int(x) for x in input().split()]
	if S1[0] == 1:
		S2.append(S1[1])
	if S1[1] == N:
		S2.append(S1[0])
		
if len(S2) == len(set(S2)):
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

Submission status: Accepted

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


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

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

l = list(set(d) & set(e))

if l == []:
	print('IMPOSSIBLE')
else:
	print('POSSIBLE')

Submission status: Accepted

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

x=[]
y=[]

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


set_x = set(x)
set_y = set(y)
z = list(set_x & set_y)

if(len(z)>0):
	ans="POSSIBLE"
else:
	ans="IMPOSSIBLE"

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split()]

boat = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(v) for v in input().split()]
    boat[a-1].append(b-1)
    boat[b-1].append(a-1)
    
ans = False
for island in boat[N-1]:
    ans |= any(t == 0 for t in boat[island])
    
print ("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

n, m = list(map(int, input().split()))
mid_set1 = set([])
mid_set2 = set([])

for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        mid_set1.add(b)
    elif b == n:
        mid_set2.add(a)

if len(mid_set1&mid_set2) > 0:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

p1 = []
p2 = []
def solve():
    for i in range(M):
        a,b = map(int, input().split())
        if a == 1:
            p1.append(b)
        elif b == N:
            p2.append(a)
    return len(set(p1) & set(p2)) > 0

print('POSSIBLE' if solve() else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
abstart=[]
abgoal=[]
for i in range(0,m):
    inp=[int(i) for i in input().split()]
    if inp[0]==1:
        abstart.append(inp[1])
    elif inp[1]==n:
        abgoal.append(inp[0])

start = set(abstart)
goal = set(abgoal)
matched = list(start & goal)

if len(matched)>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
  N,M = map(int,input().split())
  m = set()
  for _ in range(M):
    a,b = map(int,input().split())
    if a < b:
      m.add((a,b))
    else:
      m.add((b,a))
  for i in range(2,N):
    if (1,i) in m and (i,N) in m:
      print('POSSIBLE')
      break
  else:
    print('IMPOSSIBLE')

main()

Submission status: Accepted

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

    loot = { x:set() for x in range(1, n+1)}
    for l in ship_loot:
        a, b = l
        loot[a].add(b)
        loot[b].add(a)

    print('POSSIBLE' if loot[1] & loot[n] else 'IMPOSSIBLE')
    # print(ship_loot)
    # print(loot)
    # print(loot[1] & loot[n])

c()

Submission status: Accepted

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

m_1=[0]*(N+1)
m_N=[0]*(N+1)
for _ in range(M):
    a,b=map(int,raw_input().split(' '))
    if a==1:
        m_1[b]=1
    if b==N:
        m_N[a]=1

a=''.join(map(str,m_1))
b=''.join(map(str,m_N))

c=int(a,2)
d=int(b,2)


if c&d==0:
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.append(b)
    elif b == n:
        e.append(a)
if len(set(s) & set(e)) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
edge = dict()
for i in range(1,N+1):
    edge[i] = set()
for i in range(M):
    a, b = [int(i) for i in input().split()]
    edge[a].add(b)
    edge[b].add(a)
c = edge[1].intersection(edge[N])
if len(c) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
nums=[int(x) for x in input().split()]
V,E = nums[0],nums[1]
graph = {x:[] for x in range(V)}

for i in range(E):
    nums=[int(x) for x in input().split()]
    a,b = nums[0]-1,nums[1]-1
    graph[a].append(b)
    graph[b].append(a)


if __name__ == '__main__':
	goal = V - 1
	mids = graph[0]
	for isl in mids:
		if goal in graph[isl]:
			print("POSSIBLE")
			exit(0)
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
ships_1 = []
ships_2 = []
for m in range(M):
    tmp = list(map(int,input().split()))
    if tmp[0]==1:
        ships_1.append(tmp[1])
    elif tmp[1] == N:
        ships_2.append(tmp[0])

matched_list = list(set(ships_1) & set(ships_2))
if matched_list:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# coding: utf-8

if __name__ == "__main__":
    n, m = map(int, input().split())

    connected_1 = []
    connected_n = []

    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            connected_1.append(b)
            continue
        elif a == n:
            connected_n.append(b)
            continue
        elif b == 1:
            connected_1.append(a)
            continue
        elif b == n:
            connected_n.append(a)
            continue
        else:
            continue

    if len(set(connected_1).intersection(set(connected_n))) >= 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Submission status: Accepted

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

if set(n) & set(o):
    print ('POSSIBLE')
else:
    print ('IMPOSSIBLE')

Submission status: Accepted

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

rl = [[] for x in range(n + 1)]

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

now = 1
next_node = rl[now]
if n in next_node or n == 1:
    print("POSSIBLE")
    __import__("sys").exit()


for node in next_node:
    if n in rl[node]:
        print("POSSIBLE")
        __import__("sys").exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

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

aa = []
bb = []

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

    if b == n:
        bb.append(a)

aa = set(aa)
bb = set(bb)

ret = aa & bb

if len(ret) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
# encoding:utf-8

def main():
	n, m = list(map(int, input().split()))
	ships = [list(map(int, input().split())) for _ in range(m)]
	frm1 = [x[1] for x in ships if x[0] == 1]
	toN = [x[0] for x in ships if x[1] == n]
	out = set(frm1).intersection(set(toN))
	if len(out) >= 1:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
		
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split(" "))
frs = {}
tos = {}
for m in xrange(M):
  fr, to = map(int, raw_input().split(" "))
  if fr == 1:
    if to in tos:
      print "POSSIBLE"
      break
    frs[to] = 1
  elif to == N:
    if fr in frs:
      print "POSSIBLE"
      break
    tos[fr] = 1
else:
  print "IMPOSSIBLE"

Submission status: Accepted

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

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)



def main():
    N, M = map(int, input().split())

    mid1 = set()
    mid2 = set()
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            mid1.add(b)
        elif b == N:
            mid2.add(a)

    result = bool(mid1 & mid2)
    print("POSSIBLE" if result else "IMPOSSIBLE")

if __name__ == "__main__": main()

Submission status: Accepted

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

graph = [list() for i in range(N+1)]
for i in range(M):
    a, b = tuple(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

pos_flag = False
for u in graph[1]:
    if N in graph[u]:
        pos_flag = True
        break
if pos_flag == True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == 1:
    a_list.append(X[i][0])
  elif X[i][0] == n:
    b_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list) & set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == 1:
    a_list.append(X[i][0])
  elif X[i][0] == n:
    b_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list)&set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == 1:
    a_list.append(X[i][0])
  elif X[i][0] == n:
    b_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_dic = {a_list}&{b_list}
if len(c_dic) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] = 1:
    a_list.append(X[i][1])
  elif X[i][1] = 1:
    a_list.append(X[i][0])
  elif X[i][0] = n:
    b_list.append(X[i][1])
  elif X[i][1] = n:
    b_list.append(X[i][0])
c_dic = {a_list}&{b_list}
if len(c_dic) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setParent(self, other: 'Island') -> None:
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    root.setAsRoot()
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setParent(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    #諸島生成
    islands: Islands = Islands(N)
    #諸島間定期便生成
    for a, b in ab:
        islands[a].addConnection(islands[b])
    #bfs
    bfs(islands[1], 2)
    #出力
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,m = i_map()
    c = [[10]*n for _ in range(n)]

    for _ in range(m):
        a,b = i_map()
        c[a-1][b-1] = 1
        c[b-1][a-1] = 1

    for i,k in enumerate(c[0]):
        if k == 1:
            if c[i][-1] == 1:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE")


if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline()
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edg=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a][b]=1
    edg[b][a]=1
f=1
for i in range(2,n+1):
    if edg[i][1]==1 and edg[i][n]==1:
        f=0
print("POSSIBLE" if f==0 else "IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
#55 C - Cat Snuke and a Voyage
import collections from deque
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Runtime Error

Solution code:
#55 C - Cat Snuke and a Voyage
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Runtime Error

Solution code:
#55 C - Cat Snuke and a Voyage
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
print(G)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def main():
  N, M = map(int,input().split())
  fromOne = set()
  toM = set()
  for i in range(N):
    a, b = map(int,input().split())
    if a == 1:
      fromOne.add(b)
    elif b == M:
      toM.add(a)
  return 'POSSIBLE' if fromOne & toM else 'IMPOSSIBLE'
print(main())

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]
dist = [float('inf')]*N

def dfs(u, pre, cnt):
  dist[u] = cnt
  for v in graph[u]:
    if v != pre and cnt+1 < dist[v]:
      dfs(v, u, cnt+1)

    
dfs(0, -1, 0)
if 0 < dist[N-1] <= 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
M=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    M.append([a,b])
yes="POSSIBLE";no="IMPOSSIBLE"

for i in M[0]:
    if n-1 in M[i]:
        print(yes);exit()
print(no)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(m):
    a,b=input().split()
    ab.append([int(a),int(b)])    
c = []
ab=list(set(ab))
for j in range(len(ab)):
    if ab[j][0]==1:
        c.append(ab[j][1])
for p in range(len(ab)):
    if ab[p][1] == n and ab[p][0] in c:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
N, M = map(int, input())
From = set()
To = set()
for _ in range(M):
  a, b = map(int, input())
  if a == 1:
    From.add(b)
  if b == N:
    To.add(a)
if From.isdisjoint(To):
  print("INPOSSIBLE")
else:
  print("POOSIBLE")

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
A = np.zeros((n,n),dtype=np.bool)
for i in range(m):
    a,b = map(int,input().split())
    A[a-1,b-1] = 1
    
if 1 in A[A[0] == 1,n-1]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
A = np.zeros((n,n),dtype=np.int8)
for i in range(m):
    a,b = map(int,input().split())
    A[a-1,b-1] = 1
    
if 1 in A[A[0] == 1,n-1]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
A = np.zeros((n,n),dtype=np.int8)
for i in range(m):
    a,b = map(int,input().split())
    A[a-1,b-1] = 1
    A[b-1,a-1] = 1
print(A)
if 1 in A[np.where(A[0] == 1),n-1][0]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
A = np.zeros((n,n),dtype=np.int8)
for i in range(m):
    a,b = map(int,input().split())
    A[a-1,b-1] = 1
if 1 in A[np.where(A[0] == 1),n-1][0]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
A = np.zeros((n,n),dtype=np.int8)
for i in range(m):
    a,b = map(int,input().split())
    A[a-1,b-1] = 1
if 1 in A[np.where(A[0] == 1),n-1]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
A = np.zeros((n,n),dtype=np.bool)
for i in range(m):
    a,b = map(int,input().split())
    A[a-1,b-1] = 1

if 1 in A[np.where(A[0] == 1),n-1]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
4 3
1 4
4 5
2 3

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
x=[]
y=[]
for i in lst:
  if lst[0]==1:
    x+=[i[1]]
for i in lst:
  if lst[1]==n:
    y+=[i[0]]
ans='IMPOSSIBLE'
for i in x:
  if i in y:
    ans='POSSIBLE'
    break
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
x=[]
y=[]
for i in lst:
  if lst[0]==1:
    x+=[i[1]]
for i in lst:
  if lst[1]==n:
    y+=[i[0]]
ans='IMPOSSIBLE'
for i in x:
  if i in y:
    ans='POSSIBLE'
    break
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
x=[]
y=[]
for i in lst:
  if lst[0]==1:
    x+=[lst[1]]
for i in lst:
  if lst[1]==n:
    y+=[lst[0]]
ans='IMPOSSIBLE'
for i in x:
  if i in y:
    ans='POSSIBLE'
    break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): sys.stdin.readline().strip()
N, M = map(int, input().split())
li_s = []
li_g = []

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

for x in li_s:
    if x in li_g:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Runtime Error

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

for i in c[1]:
  if n in c[i]:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    if(a == 0):
        return b
    return gcd(b % a, a)
def lcm(a, b):
    return a // gcd(a, b) * b
t = int(input())
ans = 1
while(t != 0):
    t -= 1
    n = int(input())
    ans = lcm(ans, n)
print(int(ans))

Submission status: Runtime Error

Solution code:
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 2e5 + 1;
// int a[N][N];
int main(){
    speed;
    int n, m;
    cin >> n >> m;
    vi a, b;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        if(x == 1){
            a.pb(y);
        }
        if(y == n){
            b.pb(x);
        }
    }
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            if(a[i] == b[j]){
                cout << "POSSIBLE";
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE";
}

Submission status: Runtime Error

Solution code:
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 2e5 + 1;
int a[N][N];
int main(){
    speed;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for(int i = 0; i < N; ++i){
        if(a[1][i] && a[i][n]){
            cout << "POSSIBLE";
            return 0;
        }
    }
    cout << "IMPOSSIBLE";
}

Submission status: Runtime Error

Solution code:
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 1e5 + 1;
int a[N][N];
int main(){
    speed;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for(int i = 0; i < N; ++i){
        if(a[1][i] && a[i][n]){
            cout << "POSSIBLE";
            return 0;
        }
    }
    cout << "IMPOSSIBLE";
}

Submission status: Runtime Error

Solution code:
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 1e4 + 1;
int a[N][N];
int main(){
    speed;
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for(int i = 0; i < N; ++i){
        if(a[1][i] && a[i][n]){
            cout << "POSSIBLE";
            return 0;
        }
    }
    cout << "IMPOSSIBLE";
}

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split())
    if(a[0]==1):
        pass_1.append(a[1])
    else:
        a_list.append(a)
    
for j in pass_1:
    if([j,N] in a):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Runtime Error

Solution code:
import bisect
N, M = map(int, input().split())
start_to_middle = []
middle_to_end = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        start_to_middle.append(b)
    elif b == N:
        middle_to_end.append(a)
if not len(start_to_middle) or not len(middle_to_end):
    print('IMPOSSIBLE')
    exit()
middle_to_end.sort()
for middle in start_to_middle:
    idx = bisect.bisect_left(middle_to_end, middle)
    if middle_to_end[idx] == middle:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')