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())
ab = [list(map(int, input().split())) for i in range(M)]

island_go_from_1 = set()
island_go_to_N = set()
for i in range(M):
    if ab[i][0] == 1:
        island_go_from_1.add(ab[i][1])
    if ab[i][1] == N:
        island_go_to_N.add(ab[i][0])

ans = island_go_from_1 & island_go_to_N
if len(ans) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
island, ship = map(int, input().split())
startTo, fromGoal = [False] * island, [False] * island
for i in range(ship):
  a, b = map(int, input().split())
  if a == 1:
    startTo[b - 1] = True
  elif b == 1:
    startTo[a - 1] = True
  elif a == island:
    fromGoal[b - 1] = True
  elif b == island:
    fromGoal[a - 1] = True
check = False
for i in range(island):
  if startTo[i] and fromGoal[i]:
    check = True
    break
if check:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
start = set()
goal = set()
for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        start.add(b)
    elif  b == n:
        goal.add(a)

ans = start & goal
if len(ans) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

se1 = set()
se2 = set()

for a, b in ls:
    if a == 1:
        se1.add(b)
    if b == n:
        se2.add(a)

se = se1 & se2

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(set)
for _ in range(M):
    src, dst = map(int, input().split())
    d[src].add(dst)

ans = False
for x in d[1]:
    if N in d[x]:
        ans = True
        break
print("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

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

N, M = map(int, input().split())
ship1 = set([])
ship2 = set([])
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        ship1.add(b)
    elif b == N:
        ship2.add(a)

if ship1 & ship2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ship1 = set([])
ship2 = set([])
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        ship1.add(b)
    elif b == N:
        ship2.add(a)

if len(ship1 & ship2) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[[int(x) for x in input().split()] for _ in range(M)]
sa=set()
en=set()
for a,b in AB:
    if a>b:
        a,b=b,a
    if a==1:
        sa.add(b)
    if b==N:
        en.add(a)
print('POSSIBLE' if sa&en else 'IMPOSSIBLE')

Submission status: Accepted

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

for m in range(M):
    a,b = list(map(int,input().split()))
    if a==1:
      x|=1<<b
    if b==N:
      y|=1<<a

print("IM"*(x&y==1)+"POSSIBLE")

Submission status: Accepted

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

start_1 = set([])
goal_N = set([])

for i in range(M):
    if ab[i][0] == 1:
        start_1.add(ab[i][1])
    if ab[i][1] == N:
        goal_N.add(ab[i][0])

ans = start_1 & goal_N
if len(ans) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
transit_a = set()
transit_b = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        transit_b.add(b)
    elif b == n:
        transit_a.add(a)

print('POSSIBLE' if len(transit_a & transit_b) else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
transit_a = set()
transit_b = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        transit_b |= {b}
    elif b == n:
        transit_a |= {a}

print('POSSIBLE' if len(transit_a & transit_b) else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = {tuple(map(int, input().split())) for _ in range(m)}

for i in range(2, n):
    route = [1, i, n]
    if all(edge in s for edge in zip(route, route[1:])):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

import numpy as np

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

start = np.zeros(n)
end = np.zeros(n)
for a, b in ab:
    if a == 1:
        start[b-1] = 1
    if b == n:
        end[a-1] = 1

ans = np.any((start * end))
print("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

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

A=[]
B=[]
for ab in AB:
  if ab[0]==1:
    A.append(ab[1])
  if ab[1]==N:
    B.append(ab[0])
#print(A)
#print(B)
C=list(set(A+B))
#print(C)

print("IMPOSSIBLE" if len(C)==len(A)+len(B) else "POSSIBLE")

Submission status: Accepted

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

from0 = edge[0]
flag = 'IMPOSSIBLE'
for i in from0:
    if n-1 in edge[i]:
        flag = 'POSSIBLE'
print(flag)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ss = [False for _ in range(n + 1)]
ts = [False for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ss[b] = True
    if b == n:
        ts[a] = True
ok = False
for i in range(n):
    if ss[i] and ts[i]:
        ok = True
        break
if ok:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(M):
    data.append([int(x) for x in stdin.readline().rstrip().split()])
shima = set()

flag = False
for i in sorted(data):
    if i[0] == 1:
        shima.add(i[1])
    if (i[1] == N) and (i[0] in shima):
        flag = True
        break

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

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
##############################

from collections import deque

N, M = map(int, input().split())
cost = [ [] for _ in range(N) ]
visited = [False] * N

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

#print(cost)

def bfs(node, dist):
    d = deque()
    d.append( (node, dist) )

    while d:
        (node, dist) = d.popleft()
        if visited[node] != False:
            continue

        visited[node] = dist

        for i in cost[node]:
            d.append((i, dist+1))

    return visited[N-1]


if bfs(0, 0) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
##############################

from collections import deque

N, M = map(int, input().split())
cost = [ [] for _ in range(N) ]
visited = [False] * N

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

#print(cost)

def bfs(node, dist):
    d = deque()
    d.append( (node, dist) )

    while d:
        (node, dist) = d.popleft()
        if visited[node] != False:
            continue

        visited[node] = dist

        for i in cost[node]:
            d.append((i, dist+1))

    return visited[-1]


if bfs(0, 0) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
from_one = [0] * n
to_n = [0] * n

for _ in range(m):
    a, b = na()
    if a == 1:
        from_one[b] = 1
    if b == n:
        to_n[a] = 1

p = False
for i, j in zip(from_one, to_n):
    if i == 1 and j ==1:
        print("POSSIBLE")
        p = True
        break
if not p:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict


def resolve():
    n, m = list(map(int, input().split()))
    d = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        d[a].append(b)
    if n in d[1]:
        print("POSSIBLE")
        return 0
    for i in d[1]:
        if n in d[i]:
            print("POSSIBLE")
            return 0
    print("IMPOSSIBLE")
    return 0


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, M = tuple(map(int, input().split()))
A, B = [], []
for _ in range(M):
    a, b = tuple(map(int, input().split()))
    A.append(a)
    B.append(b)
path1 = set()
path2 = set()
for a, b in zip(A, B):
    if a == 1:
        path1.add(b)
    if b == N:
        path2.add(a)
if len(path1.intersection(path2)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = [[] for _ in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    a[x-1] += [y-1]
for i in a[0]:
    for j in a[i]:
        if j == n-1 :
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
l1=[False]*n
ln=[False]*n
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        l1[b-1]=True
    if b==1:
        l1[a-1]=True
    if a==n:
        ln[b-1]=True
    if b==n:
        ln[a-1]=True
for i in range(n):
    if l1[i] and ln[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
ab.sort()
mid = []
cand = []
for i in range(m):
  if ab[i][0] == 1:
    mid.append(ab[i][1])
  elif ab[i][0] == n:
    cand.append(ab[i][1])
  elif ab[i][1] == n:
    cand.append(ab[i][0])    

if len(set(mid) & set(cand)) > 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())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    p1 = [0]*N
    for a in A:
        if a[0] == 1:
            p1[a[1]] = 1
    for a in A:
        if a[1] == N and p1[a[0]]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N,M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    p1 = set()
    for a in A:
        if a[0] == 1:
            p1.add(a[1])
    for a in A:
        if a[1] == N and a[0] in p1:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

fst = []
scnd = {}

for i in ab:
  if i[0]==1:
    fst.append(i[1])
  if N in i:
    idx = i.index(N)
    scnd[i[1-idx]] = 0

#print(scnd,fst)
    
for j in fst:
  if j in scnd:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
N, M = [int(x) for x in input().split()]
fst_to = deque([])
sec_from = deque([])
for a, b in [[int(x) for x in input().split()] for _ in range(M)]:
  if a == 1:
    fst_to.append(b)
  elif b == N:
    sec_from.append(a)
ret = 'IMPOSSIBLE'
if set(fst_to) & set(sec_from):
  ret = 'POSSIBLE'
print(ret)

Submission status: Accepted

Solution code:
n,m,*l=map(int,open(0).read().split())
a=set();b=set()
for i,j in sorted(zip(*[iter(l)]*2)):
	if i==1:a.add(j)
	if j==n:b.add(i)
print("POSSIBLE"if a&b else"IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a not in g:
        g[a] = [b]
    if b not in g:
        g[b] = [a]
    if a in g:
        g[a].append(b)
    if b in g:
        g[b].append(a)
ans = "IMPOSSIBLE"
for i in g[1]:
    if n in g[i]:
        ans = "POSSIBLE"
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
X = set()
Y = set()
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        X.add(b)
    if b == n:
        Y.add(a) 
print("IMPOSSIBLE" if not X&Y else "POSSIBLE")

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
f = []
t = []
for i in range(m):
    a,b = inpl()
    if a == 1:
        f.append(b)
    elif b == n:
        t.append(a)
t = set(t)
for i in f:
    if i in t:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

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

A = [list(map(int, input().split())) for _ in range(M)]
B = []

for i in range(M):
	if 1 in A[i]:
		B.append(A[i][1])
	elif N in A[i]:
		B.append(A[i][0])

C = set(B)

if len(C) == len(B):
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
path = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in path:
        path[a] = [b]
    else:
        path[a].append(b)

ns = []
if 1 in path:
    for p in path[1]:
        ns.append(p)

    flag = False
    for mid in ns:
        if mid in path:
            if n in path[mid]:
                flag = True
                break

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

else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from1 = set()
toN = set()
for _ in range(M):
  a, b = map(int, input().split())
  if a == 1:
    from1.add(b)
  elif b == N:
    toN.add(a)
if from1 & toN:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
ab = []
for _ in range(m):
    a,b = map(int, input().split())
    if a==1:
        ab.append(b)
    elif b==n:
        ab.append(a)
print('POSSIBLE' if len(ab)-len(set(ab)) != 0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dic = {}
for i in range(1, n+1):
  dic[i] = []
for i in range(m):
  a1, a2 = map(int, input().split())
  dic[a1] += [a2]
  dic[a2] += [a1]

Places_from1 = dic[1]
for place in Places_from1:
  if n in dic[place]:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
ABs = list([list(map(int,input().split())) for _ in range(M)])
 
ship1 =[]
shipn =[]
 
for ab in ABs:
    if ab[0]==1:ship1.append(ab[1])
    elif ab[1]==N:shipn.append(ab[0])
 
      
if list(set(ship1) & set(shipn)) ==[]:print('IMPOSSIBLE')
else:print('POSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
ABs = list([list(map(int,input().split())) for _ in range(M)])
 
ship1 =[]
shipn =[]
 
for ab in ABs:
    if ab[0]==1:ship1.append(ab[1])
    elif ab[1]==N:shipn.append(ab[0])
 
      
if list(set(ship1) & set(shipn)) ==[]:print('IMPOSSIBLE')
else:print('POSSIBLE')

Submission status: Accepted

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

class Node:
    def __init__(self, id):
        self.id = id
        self.link = []
        self.check = False

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

    nodes = [Node(i) for i in range(N+1)]

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

    ok = False
    q = deque()
    q.append((nodes[1], 0))
    nodes[1].check
    while len(q) > 0:
        node, cost = q.popleft()
        if node.id == N:
            ok = True
            break
        if cost <= 1:
            for nex in node.link:
                if not nex.check:
                    q.append((nex, cost+1))
                    nex.check = True
    
    if ok:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(m)]

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

for a,b in ab:
    li[a].append(b)

li2=[]
for i in li[1]:
    li2.append(i)

ans=False
for i in li2:
    if n in li[i]:
        ans=True
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Accepted

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

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

for a,b in ab:
    li[a].append(b)

li2=[]
for i in li[1]:
    li2.append(i)

ans=False
for i in li2:
    if n in li[i]:
        ans=True
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Accepted

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
edges = {}
flag = 'IMPOSSIBLE'
for a, b in AB:
    if a in edges:
        edges[a].append(b)
    else:
        edges[a] = [b]
for i in edges[1]:
    if i not in edges:
        continue
    if N in edges[i]:
        flag = 'POSSIBLE'
        break

print(flag)

Submission status: Accepted

Solution code:
import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def dfs(v):
    global ct
    visit[v][0] = True
    for next in g[v]:
        if visit[next][0]:
            continue
        else:
            visit[next][1] = visit[v][1] + 1
            if visit[next][1] >= 3:
                continue
            dfs(next)
n, m = na()
g = [[] for i in range(n)]
for i in range(m):
    a, b = na()
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

visit = [[False, 0] for i in range(n)]
ct = 0
dfs(0)
print('POSSIBLE' if visit[n - 1][0] and visit[n - 1][1] <= 2 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = [int(el) for el in input().split(' ')]
ships = []
for _ in range(m):
    ships.append([int(el) for el in input().split(' ')])

S = set()
T = set()

for ship in ships:
    a = ship[0]
    b = ship[1]
    if a == 1:
        S.add(b)
    if b == n:
        T.add(a)

if S.intersection(T):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int, input().strip().split(' '))
front = set()
rear = set()
for _ in range(M):
  a,b = map(int, input().strip().split(' '))
  if a == 1:
    front.add(b)
  if b == N:
    rear.add(a)

print('POSSIBLE' if len(front&rear) > 0 else 'IMPOSSIBLE')

Submission status: Accepted

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

sa = set()
sb = set()


for i in range(M):

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

    if a==1:
        sa.add(b)
    elif b==N:
        sb.add(a)

print("POSSIBLE" if len(sa&sb)!=0 else "IMPOSSIBLE")

Submission status: Accepted

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

ans = "IMPOSSIBLE"
list1 = [0] * N
listN = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        list1[b] = 1
    elif b == N :
        listN[a] = 1

for i in range(N):
    if list1[i] == 1 and listN[i] == 1:
        ans = "POSSIBLE"
        break

print(ans)

Submission status: Accepted

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

s1 = []
sn = []

for i in range(m):
    if A[i][0] == 1:
        s1.append(A[i][1])
    elif A[i][1] == n:
        sn.append(A[i][0])

#print(s1, sn)
if len(set(s1) & set(sn)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dfs(now,prev,count):
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if count<=2:
            if next != prev:
                if next== n-1:
                    if count==2:
                        print('POSSIBLE')
                        exit()
                    else:
                        break
                dfs(next,now,count)
 
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
dfs(0,-1,0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
start,end=set(),set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1: start.add(b)
    if b==N: end.add(a)
print("POSSIBLE" if start&end else "IMPOSSIBLE")

Submission status: Accepted

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

if len(b)==len(set(b)):
  ans='IMPOSSIBLE'
else:
  ans='POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=set()
B=set()
for i in range(m):
  a,b=input().split()
  if a=="1":
    A.add(b)
  if b==str(n):
    B.add(a)
print("POSSIBLE" if A&B else "IMPOSSIBLE")

Submission status: Accepted

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

ans="IMPOSSIBLE"
for i in ship[0]:
    if n-1 in ship[i]:
        ans="POSSIBLE"
        break
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
sa = set()
sb = set()
for i in range(m):
  a, b = map(int,input().split())
  if a == 1:
    sb.add(b)
  if b == n:
    sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Accepted

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:
        g[a].append(b)
        g[b].append(a)

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

#g[4].sort()

#print(g[4])

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

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

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[]
g=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        s.append(b)
    elif b==N:
        g.append(a)
s.sort()
g.sort()
S=len(s)
G=len(g)
x,y=0,0
while x<S and y<G:
    if s[x]>g[y]:
        y+=1
    elif s[x]<g[y]:
        x+=1
    else:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

def check():
    halfways = [0 for _ in range(N)]
    for a,b in ab_list:
        if a==1:
            halfways[b] = 1
    for a,b in ab_list:
        if b==N:
            if halfways[a] == 1:
                return True
    return False

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
c = [False] * N
d = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        c[b - 1] = True
    if b == N:
        d[a - 1] = True
ans = any([c[i] and d[i] for i in range(N)])
print("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc068/tasks/arc079_a
# C - Cat Snuke and a Voyage

n, m = list(map(int, input().split()))
ab_list = []

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

ab_dict = {k: [] for k in range(1, m+1)}

# 1と接続している島
via_nodes_1 = set([b for a, b in ab_list if a == 1])
via_nodes_2 = set([a for a, b in ab_list if b == n])

# 積集合があるか
via_nodes = via_nodes_1 & via_nodes_2

if len(via_nodes):
    ans = 'POSSIBLE'
else:
    ans = 'IMPOSSIBLE'

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = [set() for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  E[a].add(b)
  E[b].add(a)
ok = False
c = 0
ns = E[c]
for n in ns:
  ns2 = E[n]
  if N-1 in ns2:
    ok = True
    break
if ok:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    cur = [1]
    visited = set([1])
    for _ in range(2):
        temp = []
        for i in cur:
            for j in graph[i]:
                if j not in visited:
                    temp.append(j)
                    visited.add(j)
        cur = temp
    if N in cur:
        return "POSSIBLE"
    return "IMPOSSIBLE"
if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        sb.add(b)
    if b == n:
        sa.add(a)

print('IMPOSSIBLE' if len(sa & sb) == 0 else 'POSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
sa=set()
sb=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:sb.add(b)
    if b==N:sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Accepted

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


s = set()
for x in ab:
    if n in x:
        if x.index(n) == 0:
            s.add(x[1])
        else:
            s.add(x[0])

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

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
ans = "IMPOSSIBLE"
links = [[]for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    links[a].append(b)
    links[b].append(a)
for i in links[1]:

    if N in links[i]:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s_a=set()
s_b=set()
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    s_b.add(b)
  if b==n:
    s_a.add(a)
print("IMPOSSIBLE" if len(s_a&s_b)==0 else "POSSIBLE")

Submission status: Accepted

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

def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(M))
    S, D = set(), set()  # start, destination
    for a, b in A:
        if a == 1:
            S |= {b}
        if b == N:
            D |= {a}
    print("POSSIBLE" if S & D else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(M))
    S, D = set(), set()  # start, destination
    for a, b in A:
        if a == 1:
            S.add(b)
        if b == N:
            D.add(a)
    flg = S & D  # if the same X in both S & D -> possible
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(M))
    S, D = set(), set()  # start, destination
    for a, b in A:
        if a == 1:
            S |= {b}
        if b == N:
            D |= {a}
    flg = S & D  # if the same X in both S & D -> possible
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()