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())
src = [tuple(map(int,input().split())) for i in range(M)]
s1 = set()
sn = set()
for a,b in src:
    if a == 1:
        s1.add(b)
    elif a == N:
        sn.add(b)
    if b == 1:
        s1.add(a)
    elif b == N:
        sn.add(a)
ok = len(s1 & sn) > 0
print('POSSIBLE' if ok else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mid, las = [], []
ans = 0

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

if len(set(mid) & set(las)) != 0:
    ans =1

print('POSSIBLE' if ans == 1 else 'IMPOSSIBLE')

Submission status: Accepted

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

s = 1
stack = []
ans = 'IMPOSSIBLE'
if adj[s]:
    stack.extend(adj[s])
    for nextild in stack:
        if n in adj[nextild]:
            ans = 'POSSIBLE'
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush

input = sys.stdin.readline

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


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for i in range(M):
    a, b = map(int, input().split())
    g.add_edge(a - 1, b - 1)
    g.add_edge(b - 1, a - 1)
d = Dijkstra(g, 0)
if d.shortest_distance(N - 1) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
fn = lambda: map(int, input().split())
N, M = fn()
a, b = [0]*M, [0]*M
ones, goals = set(), set()
for i in range(M):
    ai, bi = fn()
    if ai == 1 and bi == N:
        print('POSSIBLE')
        exit()
    elif ai == 1:
        ones.add(bi)
    elif bi == N:
        goals.add(ai)

if len(ones.intersection(goals)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
V = [[0, 0] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    V[b - 1][0] = 1
  if b == 1:
    V[a - 1][0] = 1
  if a == N:
    V[b - 1][1] = 1
  if b == N:
    V[a - 1][1] = 1
for v in V:
  if v[0] and v[1]:
    print('POSSIBLE')
    break
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
g = []
for _ in range(m):
    A, B = map(int, input().split())
    if A == 1 or B == 1:
        s.append(A * B)
    elif A == n or B == n:
        g.append(A + B - n)
if len(set(s) & set(g)) == 0:
    print("IM", end="")
print("POSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = []
ans = -1
for i in range(M):
    a, b = map(int, input().split())
    ab.append([min(a, b), max(a, b)])
root_1i = [0 for i in range(N)]
root_iN = [0 for i in range(N)]
ab.sort()
for i in ab:
    if i[0] == 1:
        root_1i[i[1] - 1] = 1          
    elif i[1] == N and root_1i[i[0] - 1] == 1:
        print("POSSIBLE")
        ans = 1
        break
#print(root_1i)
if ans == -1:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


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

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

    for a in s:
        if a in t:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC068C
N, M=map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
#島リストを作る（N個）
island_score=[0]*N
#船の出発元aを調べる。（M回） aが1なら、島リストのb番目を+1
for i in range(M):
    if ab[i][0]==1:
        island_score[ab[i][1]]+=1
#船の行き先bを調べる。（M回)  bがNなら、島リストのa番目を調べる
for i in range(M):
    if ab[i][1]==N:
        # 島リストのがすでに1になっているならそれが経路の候補。
        if island_score[ab[i][0]]==1:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
first = set()
second = set()

for l in line:
    if end in l:
        second.add(l[0])
        second.add(l[1])
    elif start in l:
        first.add(l[1])
        first.add(l[0])


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

print('IMPOSSIBLE')

Submission status: Accepted

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

    islands_to_1 = [0 for _ in range(n+1)]
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1[boat[1]] = 1

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_n in islands_to_n:
        if islands_to_1[island_to_n] == 1:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]
b=set()
for i,j in ab:
    if i==1 or j==N:
        b.add((i,j))
print("IM"*(not(any(((1,i) in b and (i,N) in b) for i in range(N))))+"POSSIBLE")

Submission status: Accepted

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

forw = set()
backw = set()

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

if len(forw&backw) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

connect_1 = {}
connect_n = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        connect_1[b] = 1
    if b == n:
        connect_n[a] = 1
# print(connect_1.keys(), connect_n.keys())

ans = 'IMPOSSIBLE'
for k in connect_1.keys():
    if k in connect_n.keys():
        ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


# --------------------------------------------

dp = None


def main():
    N, M = li_input()
    L = []

    for i in range(M):
        a, b = li_input()

        if a == 1:
            L.append(b)

        if b == N:
            L.append(a)

    if len(L) == len(set(L)):
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")


main()

Submission status: Accepted

Solution code:
n, m = [int(v) for v in input().split()]
from_one = []
to_n = {}
for i in range(m):
    a, b = [int(v) for v in input().split()]
    if a == 1:
        from_one.append(b)
    elif b == n:
        to_n[a] = True

ans = 'IMPOSSIBLE'
for v in from_one:
    if v in to_n:
        ans = 'POSSIBLE'

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
X = [0] * N
Y = [0] * N
for i in range(M):
    S, E = list(map(int, input().split()))
    if S == 1:
        X[E-1] = 1
    if E == N:
        Y[S-1] = 1
for i in range(N):
    if X[i] == 1 and Y[i] == 1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
fromN = set([])
from1 = set([])
ans = 'IMPOSSIBLE'
for _ in range(M):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    if a == 0:
        if b == N-1:
            ans = 'POSSIBLE'
            break
        else:
            from1.add(b)
    elif b == N-1:
        fromN.add(a)
if len( fromN & from1) != 0:
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n,m,*T=map(int,open(0).read().split())
*S,=zip(T[::2],T[1::2])
f=lambda e:set(s[e<2]for s in S if e in s)
print('IM'*(f(1)&f(n)==set())+'POSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
x=y=1
for _ in[0]*M:
    a,b=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())
dp=[[0,0]for _ in[0]*N]
for _ in[0]*M:
    a,b=map(int,input().split())
    if a==1:
        dp[b][0]+=1
    elif b==N:
        dp[a][1]+=1
for i in range(N):
    if sum(dp[i])==2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
ship = []
for _ in range(m):
    a,b = map(int,input().split())
    if a==1:
        ship.append(b)
    if b==n:
        ship.append(a)
ship = sorted(ship)
g = itertools.groupby(ship)
for k,v in g:
    if len(list(v))==2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
s1 = raw_input().split(' ')
n, m = int(s1[0]), int(s1[1])
i2il = {}
for _ in range(m):
    s = raw_input().split(' ')
    if s[0] in i2il:
        i2il[s[0]].append(s[1])
    else:
        i2il[s[0]] = [s[1]]
    if s[1] in i2il:
        i2il[s[1]].append(s[0])
    else:
        i2il[s[1]] = [s[0]]
if '1' not in i2il or s1[0] not in i2il:
    print 'IMPOSSIBLE'
else:
    mid = i2il['1']
    bhit = False
    for m in mid:
        if s1[0] in i2il[m]:
            print 'POSSIBLE'
            bhit = True
            break
    if not bhit:
        print 'IMPOSSIBLE'

Submission status: Accepted

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

N,M = map(int, sdin().split())
AB = []
for i in range(M):
    AB.append(tuple(map(int, sdin().split())))
    
to_mid = set()
from_mid = set()

for a,b in AB:
    if a==1:
        to_mid.add(b)
    if b==N:
        from_mid.add(a)
        
if to_mid & from_mid:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque

def bfs(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    que = deque([(0,start)])
    
    # 未探索のノードをqueueに入れる
    while que:
        cost, cur_node = que.popleft()
        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist

N,M = map(int, input().split())
AB = []
for i in range(M):
    AB.append(tuple(map(int, input().split())))
    
#N,M = 4,3
#AB = [(1,2),(2,3),(3,4)]

adj_list = [[] for _ in range(N)]
for a,b in AB:
    a -= 1
    b -= 1
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    
dist = bfs(adj_list, N, 0)

if dist[N-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import itertools

n, m = [int(_) for _ in input().split()]
a = []
b = []
for i in range(0, m):
    ai, bi = [int(_) for _ in input().split()]
    a.append(ai)
    b.append(bi)

first = [b[i] for i in range(0, m) if a[i] == 1]
second = [a[i] for i in range(0, m) if b[i] == n]

if set(first) & set(second):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
dd = defaultdict(int)

for i in range(M):
	a,b = inpl()
	if a == 1:
		if dd[b] == 1:
			print('POSSIBLE')
			sys.exit()
		else:
			dd[b] = 1

	if b == N:
		if dd[a] == 1:
			print('POSSIBLE')
			sys.exit()
		else:
			dd[a] = 1

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
route = defaultdict(int)
for _ in range(M):
    a, b = map(int, input().split())
    route[a, b] = 1
for i in range(2, N):
    if route[1, i] == route[i, N] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())

    arry = []
    cnt = 0
    for i in range(m):
        a, b = map(int, input().split())
        if a == 1:
            cnt += 1
            arry.append(b)
        elif b == n:
            cnt += 1
            arry.append(a)
    if len(set(arry)) < cnt:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from_one, to_n = set(), set()
for ab_i in ab:
	if ab_i[0] == 1:
		from_one.add(ab_i[1])
	elif ab_i[1] == n:
		to_n.add(ab_i[0])
	
print("POSSIBLE" if from_one & to_n else "IMPOSSIBLE")

Submission status: Accepted

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

s=d[1]
f=True
for i in s:
  if N in d[i]:
    print("POSSIBLE")
    f=False
    break
if f:print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def inpl(): return input().split()
def get_str(bl): return 'POSSIBLE' if bl else 'IMPOSSIBLE'

n, m = map(int, inpl())
M = list(tuple(map(int, inpl())) for _ in range(m))#[(a, b), ..., (a, b)]
X = list(tuple((a, b)) for a, b in M if a == 1)
Y = list(tuple((a, b)) for a, b in M if b == n)
XB = set(list(b for _, b in X))
YA = set(list(a for a, _ in Y))
print(get_str(len(XB & YA) > 0))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
t_mid = set()
f_mid = set()
for _ in range(M):
    f, t = map(int,input().split())
    if f == 1:
        t_mid.add(t)
    elif t == N:
        f_mid.add(f)

if t_mid & f_mid:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = [list(map(int,input().split())) for i in range(M)]
b = set()
for i in a:
    if i[0]==1 or i[1]==N:
        b.add((i[0],i[1]))
for i in range(2,N):
    if (1,i) in b and (i,N) in b:
    	print('POSSIBLE')
    	exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

first = []
second = []
flag = 0
end = True

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

first.sort()
second.sort()
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  firsti = 0
  secondi = 0
  while(end == True):
    if first[firsti] == second[secondi]:
      print("POSSIBLE")
      break
    elif first[firsti] < second[secondi]:
      firsti += 1
      if firsti > len(first) - 1:
        print("IMPOSSIBLE")
        break
    else:
      secondi += 1
      if secondi > len(second) - 1:
        print("IMPOSSIBLE")
        break

Submission status: Accepted

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

import heapq
from collections import defaultdict
nodes = defaultdict(list)


for e in edges:
    nodes[e[0] - 1].append((1, e[1] - 1))
    nodes[e[1] - 1].append((1, e[0] - 1))


INF = float('inf')

def dijkstra(x):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist

dist = dijkstra(0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())

shima = []
ans = "IMPOSSIBLE"

for i in range(M):
  a,b = map(int ,input().split())
  if a == 1: shima.append(b-1)
  if b == N: shima.append(a-1)
    
shima.sort()
for s,t in zip(shima[:-1],shima[1:]):
  if s == t:
    ans = "POSSIBLE"
    break
 
print(ans)

Submission status: Accepted

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

hop_before = []
hop_to = []

hop_dict = {}

for i in range(M) :
    a, b = map(int, input().split())
    
    if a == 1 :
        if b in hop_dict.keys() :
            hop_dict[b] += 1
        else :
            hop_dict[b] = 1
    if b == N :
        if a in hop_dict.keys() :
            hop_dict[a] += 1
        else :
            hop_dict[a] = 1
        
possible = False
for i in hop_dict.keys() :
    if hop_dict[i] >= 2 :
        print("POSSIBLE")
        possible = True
        break
        
if possible == False :
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

# 1からある島への便があるかを保持
transit = [False] * N
# ある島からNへの便があるかを保持
transit2 = [False] * N

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        transit[b] = True
    if b == N:
        transit2[a] = True

for i in range(N):
    if transit[i] and transit2[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

transit = []
transit2 = []
for i in range(M):
    if abM[i][0] == 1:
        transit.append(abM[i][1])
    if abM[i][1] == N:
        transit2.append(abM[i][0])

# setで共通要素の集合を取ってみる
if len(set(transit) & set(transit2)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

iki=[]
kae=[]

c=0
flag=-1

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

l=len(iki)
iki2=set(iki)
l2=len(iki2)

#print(iki)
                
if l>l2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a,b={-1},{0}
for i in range(m):
    x,y=map(int,input().split())
    if x==1: a.add(y)
    if y==n: b.add(x)
print("POSSIBLE" if (len(a&b)) else "IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a = [0 for i in range(N)]
b = [0 for i in range(N)]
for i in range(M):
    link=list(map(int,input().split()))
    link.sort()
    if link[0] == 1:
        a[link[1]-1] = 1
    if link[1] == N:
        b[link[0]-1] = 1
for i in range(N):
    if a[i]*b[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

set1 = set()
setN = set()
for a in A:
    if a[0] == 1:
        set1.add(a[1])
    elif a[1] == n:
        setN.add(a[0])

if len(set1.intersection(setN)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
import bisect
N,M=map(int,input().split())
grid = []
for i in range(M):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
pre = []
pos = []
for ships in grid:
  if ships[0] == 1:
    pre.append(ships[1])
  if ships[1] == N:
    pos.append(ships[0])
if pre == [] or pos == []:
  print('IMPOSSIBLE')
  sys.exit()
pre.sort()
pos.sort()
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return 1
    return 0
for nums in pre:
  if index(pos,nums) == 1:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M =[int(i) for i in input().split(' ')]
table = [0]*N

for i in range(M):
    a,b = [int(i) for i in input().split(' ')]
    if a==1:
        table[b-1] +=1
        if b==N:
            table[b-1] +=1
    if b==N:
        table[a-1]+=1
#    print(table)
flag = True
for i in table:
    if i==2:
        print("POSSIBLE")
        flag = False
        break

if flag:
    print("IMPOSSIBLE")

#print(table)

Submission status: Accepted

Solution code:
from collections import deque

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


# print(G)
INF = float("inf")


def BFS(G, s):
    n = len(G)
    q = deque()
    D = [INF] * n
    q.append(s)
    D[s] = 0
    while len(q) != 0:
        p = q.popleft()
        for i in G[p]:
            if D[i] == INF:
                q.append(i)
                D[i] = D[p] + 1
    if D[n - 1] == 2:
        return "POSSIBLE"
    else:
        return "IMPOSSIBLE"


print(BFS(G, 0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ahoge = []
hanege = []
for i in range(m):
    ai,bi = map(int,input().split())
    if ai == 1:
        ahoge.append(bi)
    if bi == n:
        hanege.append(ai)
ahoge.sort()
hanege.sort()
def bis(i):
    under = 0
    upper = len(hanege)-1
    while under <= upper:
        l = (under+upper)//2
        if i == hanege[l]:
            return 1
        elif i < hanege[l]:
            upper = l-1
        elif i > hanege[l]:
            under = l+1
    return 0
flag = 0
for i in ahoge:
    if bis(i) == 1:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import math

# input
N, M = map(int, input().split())
edge_lst = [list(map(int, input().split())) for _ in range(M)]

d_1 = []
d_N = []

for e in edge_lst:
    if e[0] == 1:
        d_1.append(e[1])
    if e[1] == N:
        d_N.append(e[0])

ans = list(set(d_1) & set(d_N))

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

Submission status: Accepted

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

xs = {}

for a, b in ab:
    if a == 1:
        xs[b] = 1

result = 0

for a, b in ab:
    if b == N and a in xs:
        result = 1
        break

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

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import Counter
N,M = map(int,input().split())
ab = {tuple(map(int,input().split())) for _ in range(M)}
if M == 1:
    print('IMPOSSIBLE')
    exit()
ab = [i[1] if i[0] == 1 else i[0] for i in ab if i[0] == 1 or i[1] == N]
c = Counter(ab)
if c.most_common(1)[0][1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
to = set()
fr = set()
for a,b in src:
    if a == 1: to.add(b)
    if b == N: fr.add(a)
print('POSSIBLE' if to&fr else 'IMPOSSIBLE')

Submission status: Accepted

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

first_element = set()
second_element = set()

for element in input_list:
    if element[0] == 1:
        first_element.add(element[1])
    elif element[1] == N:
        second_element.add(element[0])

if first_element & second_element:
    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)]
x,y=[],[]
for s in ab:
    if s[0]==1:
        x.append(s[1])
    if s[1]==n:
        y.append(s[0])

print("POSSIBLE" if len(set(x)&set(y))>0 else "IMPOSSIBLE")

Submission status: Accepted

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

for i in arr:
    if i[0] == 1:
        one.add(i[1])
    elif i[1] == n:
        two.add(i[0])

if len(one & two) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

q = []
for i in range(len(branch[1])):
	q.append(branch[1][i])

check = False
for i in range(len(q)):
	if n in branch[q[i]]:
		check = True
		break
if check:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
reachable = False
from_start = []
to_end = []

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

if len(set(from_start).intersection(set(to_end))) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = set()
e = 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) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    set_a = set()
    set_b = set()

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

        if a == 1:
            set_b.add(b)
        elif b == n:
            set_a.add(a)

    if set_a & set_b:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Submission status: Accepted

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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    set_a = set()
    set_b = set()

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

        if a == 1:
            set_b.add(b)
        elif b == n:
            set_a.add(a)

    if len(set_a & set_b) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

n,m = map(int, sys.stdin.readline().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)
if result:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")