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:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
import sys
input = sys.stdin.readline

def main():
    N, M = input().split()
    A = tuple(input().split() for _ in range(int(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()

Submission status: Accepted

Solution code:
# ABC068C - Cat Snuke and a Voyage (ARC079C)
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()

Submission status: Accepted

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

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


def d(s, cnt):
    if s == n and cnt <= 2:
        print('POSSIBLE')
        exit()
    else:
        for i in c[s]:
            d(i, cnt + 1)


d(1, 0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
(nodes, edges) = (int(tok) for tok in input().split())

edges_start = set()
edges_stop = set()

for _ in range(edges):
  (a, b) = (int(tok) for tok in input().split())
  if a == 1:
    edges_start.add(b)
  elif b == nodes:
    edges_stop.add(a)
    
valid = any(x in edges_stop for x in edges_start)
print("POSSIBLE" if valid else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from_1 = [False]*N
to_N = [False]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b-1] = True
    elif b == N:
        to_N[a-1] = True
for i in range(1, N):
    if from_1[i] and to_N[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

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

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

q1 = [0]
q2 = []
visited = [False] * N
visited[0] = True

while q1 :
    cur = q1.pop()
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            q2.append(nex)
            
while q2 :
    cur = q2.pop()
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
    
if visited[N-1] :
    print('POSSIBLE')
else :
    print('IMPOSSIBLE')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

que = deque()
que.append((1, 0))
ok = False
seen = [[False] * (N + 1), [False] * (N + 1)]
while que:
    v, d = que.popleft()
    if v == N and d == 2:
        ok = True
        break
    if d >= 2:
        continue
    for u in graph[v]:
        if not seen[d][u]:
            seen[d][u] = True
            que.append((u, d + 1))
if ok:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph: list, node: int, start: int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    # dist = [costs to nodes]

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

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

dist = dijkstra(edge, n, 0)
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ll = [list(map(int,input().split())) for _ in [0]*m]
to=set()
nfrom=set()
for l in ll:
  if l[0]==1:
    to.add(l[1])
  if l[1]==n:
    nfrom.add(l[0])
if len(to&nfrom)>0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [(lambda x, y:(x, y))(*map(int, input().split())) for _ in range(m)]
d = {}
for x in ab:
  if x[0] in d.keys():
    d[x[0]].append(x[1])
  else:
    d[x[0]] = [x[1]]
moyo = []
for z in d[1]:
  if z in d.keys():
    moyo += d[z]
for z in moyo:
  if z == n:
    exit(print('POSSIBLE'))
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:

n, m = [int(x) for x in input().split()]
transitions = [list(map(int,input().split())) for _ in range(m)]
one_roots = set()
second_roots = set()
for transition in transitions:
    if transition[0] == 1:
        one_roots.add(transition[1])
    if transition[1] == n:
        second_roots.add(transition[0])

print('POSSIBLE' if len(one_roots.intersection(second_roots)) > 0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque


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



from collections import deque


def dfs(path, start):
    que = deque([(start, 0)])
    dist = [float('inf')] * n
    while que:
        cur, c = que.popleft()
        c += 1
        for nxt in path[cur]:
            if c < dist[nxt]:
                dist[nxt] = c
                que.append((nxt, c))
    return dist



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

Submission status: Accepted

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

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

D1 = set(A[i][1] for i in range(M) if A[i][0] == 1)
D2 = set(A[i][0] for i in range(M) if A[i][1] == N)

if len(D1 & D2) != 0:
  print ("POSSIBLE")
else:
  print ("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l1 = [0]*n
l2 = [0]*n

for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  if a == 0:
    l1[b] = 1
  elif b == n-1:
    l2[a] = 1
  else:
    continue

for j in range(n):
  if l1[j] == 1 and l2[j] == 1:
    print('POSSIBLE')
    exit()
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
  
from collections import deque
queue = deque([])
queue.append(0)

visited = [-1]*n
visited[0] = 0

while queue:
  x = queue.popleft()
  for new_x in g[x]:
    if visited[new_x] == -1:
      if new_x == n-1 and visited[x]+1 == 2:
        print('POSSIBLE')
        exit()
      else:
        visited[new_x] = visited[x]+1
        queue.append(new_x)
    else:
      continue
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
ls = []
heapq.heapify(ls)
for i in range(m):
    if ab[i][0] == 1:
        heapq.heappush(ls, ab[i][1])
    else:
        while True:
            if len(ls) != 0:
                p = heapq.heappop(ls)
                if p == ab[i][0]:
                    if ab[i][1] == n:
                        print("POSSIBLE")
                        exit()
                    else:
                        heapq.heappush(ls, p)
                        break
                elif p > ab[i][0]:
                    heapq.heappush(ls, p)
                    break
            else:
                print("IMPOSSIBLE")
                exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
B=[list(map(int,input().split())) for _ in range(M)]
dic=defaultdict(list)
ans="IMPOSSIBLE"
for i,j in B:
  dic[i].append(j)
O=dic.get(1)
if N in O:
    ans="POSSIBLE"
for o in O:
  T=dic.get(o)
  try:
    if N in T:
      ans="POSSIBLE"
  except:
    pass
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

edges = [[] for _ in range(N)]

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

def dfs(start, end):
    minDist = [-1 for _ in range(N)]
    minDist[start] = 0

    que = deque([])
    que.append((start, 0))

    while que:
        now, dist = que.popleft()

        minDist[now] = dist
        if now == end:
            return dist

        for to in edges[now]:
            if minDist[to] >= 0:
                continue
            que.append((to, dist + 1))

    return float('inf')

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
n1 = set()
ans = "IMPOSSIBLE"
for i in range(m):
    a,b = map(int,input().split())
    if a == 1 or a == n:
        if b in n1:
            ans = "POSSIBLE"
        else:
            n1.add(b)
    elif b == 1 or b == n:
        if a in n1:
            ans = "POSSIBLE"
        else:
            n1.add(a)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

# refered to
# rank : http://at274.hatenablog.com/entry/2018/02/02/173000
# size : abc120 kaisetsu
class UnionFind:
    def __init__(self, n):
        # par = Parent Number or NoV
        self.par = [-1] * (n+1)
        # rank = Tree Height
        self.rank = [0] * (n+1)
    
    # 自分が所属する集合の数を返す
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

    # 根なら番号を返す
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    # 親が同じか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # もう繋がれている
        if(x == y):
            return False

        # つなぎ替える
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        # xのサイズを更新
        self.par[x] += self.par[y]
        # yのサイズ(おやばんごう)をxに
        self.par[y] = x

        return True 


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

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ab = sorted([[a[i], b[i]] for i in range(M)], key=lambda x:(x[0], x[1]))

    p1 = []

    for i,j in ab:
        if(i == 1):
            p1.append(j)
        else:
            break
    
    p1 = set(p1)

    for i,j in ab:
        if(i in p1 and j == N):
            print(YES)
            exit()

    print(NO)

    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
b1 = [False for i in range(n)]
bn = [False for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    if a == 0:
        b1[b] = True
    if b == n - 1:
        bn[a] = True
for i in range(n):
    if b1[i] and bn[i]:
        print("POSSIBLE")
        import sys
        sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def yes():
    print("POSSIBLE")  # type: str


def no():
    print("IMPOSSIBLE")  # type: str


import heapq
INF = float("inf")


# 無向グラフを仮定する。
class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge([aa-1, bb-1, 1])

    dist, prev = shortestPath(g, 0)
    if dist[N-1] <= 2:
        yes()
    else:
        no()
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a1 = set()
an = set()
for i in range(m):
  now = list(map(int,input().split()))
  if now[0] == 1:
    a1.add(now[1])
  elif now[0] == n:
    an.add(now[1])
  elif now[1] == 1:
    a1.add(now[0])
  elif now[1] == n:
    an.add(now[0])
a = a1 & an
if len(a) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=set([])
g=set([])
for i in range(M):
    a,b=map(int,input().split())
    if a==1:s.add(b)
    if b==N:g.add(a)
print(["IMPOSSIBLE","POSSIBLE"][len(s&g)>0])

Submission status: Accepted

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

ans = []
flag = False

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

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

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
dist[1] = 0
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
q.append(1)

while q:
    now = q.popleft()

    for itm in lst[now]:
        if dist[itm] > dist[now]:
            q.append(itm)
            dist[itm] = dist[now] + 1
print("POSSIBLE") if dist[N] <= 2 else print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
d = 0
q.append([1,d])

while q:
    now, d = q.popleft()
    dist[now] = d

    for itm in lst[now]:
        if dist[itm] > d+1:
            q.append([itm,d+1])
            
print("POSSIBLE") if dist[N] <= 2 else print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
d = 0
q.append([1,d])

while q:
    now, d = q.popleft()
    dist[now] = d
    if now == N:
        if d <= 2:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        exit()
    
    for itm in lst[now]:
        if dist[itm] > d+1:
            q.append([itm,d+1])
            
print("IMPOSSIBLE")

Submission status: Accepted

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

l = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)
ans = 'IMPOSSIBLE'
for i in l[0]:
    for j in l[i]:
        if j == N-1:
            ans = 'POSSIBLE'
            break
print(ans)

Submission status: Accepted

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


dst1 = []
dst2 = []

for i in range(m):
    if lst[i][0] == 1:
        dst1.append(lst[i][1])
    elif lst[i][1] == n:
        dst2.append(lst[i][0])

if (set(dst1) & set(dst2)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

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

print('IMPOSSIBLE')

Submission status: Accepted

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

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

print('IMPOSSIBLE')

Submission status: Accepted

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

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

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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = list(map(int,input().split()))
d = [list(map(int,input().split())) for i in range(m)]
#1から直で行ける
from_one_to = []
#nに直で行く
to_n_from = []
for i,j in d:
    if i==1:
        from_one_to.append(j)
    if j==n:
        to_n_from.append(i)
if len(set(from_one_to) & set(to_n_from)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# 2019/08/05

input=open(0).readline

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


for e in edge[-1]:
    if 0 in edge[e]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# 2019/08/05

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


for e in edge[-1]:
    if 0 in edge[e]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
E = [[] for x in range(N+1)]
visited = set()

for i in range(M):
    A, B = [int(x) for x in input().split()]
    E[A].append(B)
    E[B].append(A)

if set(E[1]) & set(E[N]):
    print("POSSIBLE")
else:
    print("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: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())
cnt = [0]*N
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        cnt[B] += 1
    elif B == N:
        cnt[A] += 1

if 2 in cnt:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

check = [[] for _ in range(N+1)]

for i in range(M):
    check[a[i]].append(b[i])
    check[b[i]].append(a[i])


a = 0

for i in range(N+1):
    if 1 in check[i] and N in check[i]:
        print('POSSIBLE')
        a = 1
        break

if a == 0:
    print('IMPOSSIBLE')

Submission status: Accepted

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

def main(N,M,visited,queue):
    ans = "IMPOSSIBLE"

    for i in queue:
        if visited[i-1] == True:
            ans = "POSSIBLE"
            break
            
    print(ans)

if __name__ == '__main__':
    N, M = map(int, input().split())
    visited,queue = [False]*N, []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1):
            visited[b-1] = True
        elif(b==N):
            queue.append(a)
    main(N,M,visited,queue)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ships = [[] for _ in range(2*10**5+1)]
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  if N in ships[_to]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    g = Graph()
    
    for i in range(M):
        a,b = inputMap()
        g.add_edge(a-1, b-1, 1)
        g.add_edge(b-1, a-1, 1)
        
    d = Dijkstra(g, 0)
    tmp = d.shortest_distance(N-1)
    
    if tmp <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
        
        
    
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):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        # startノードからgoalノードまでの最短距離
        return self.dist[goal]

    def shortest_path(self, goal):
        # startノードからgoalノードまでの最短経路
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
cnt = [0 for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cnt[b] += 1
    elif b == N:
        cnt[a] += 1
if 2 in cnt:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

n,m=map(int,input().split())
a=[]
b=[]
for _ in [0]*m:
    l=list(map(int,input().split()))
    if l[0]==1:a.append(l[1])
    if l[1]==n:b.append(l[0])
print('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')

Submission status: Accepted

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

ans = 'IMPOSSIBLE'
qs = [0]
for _ in range(2):
    qqs = []
    for q in qs:
        for n in graph[q]:
            if n == N-1:
                ans = 'POSSIBLE'
                break
            qqs.append(n)
    qs = qqs

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
route = {i + 1 : [] for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
if set(route[1]) & set(route[n]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

    # 場所1からいける場所
    s = []

    # 場所Nへいける場所
    g = []

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

    s = set(s)
    g = set(g)

    for i in s:
        if i in g:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

main()

Submission status: Accepted

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

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

if N-1 in visited:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")