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:
import sys
input = sys.stdin.readline

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

if set(ships[0]) & set(ships[-1]) == set():
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
A = set()
B = set()
for i in range(m):
    a,b = readInts()
    if a == 1:
        A.add(b)
    if b == n:
        B.add(a)
print('POSSIBLE' if A&B else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, M = inm()


def solve():
    s1 = set()
    sn = set()
    for i in range(M):
        a, b = inm()
        if a == 1:
            s1.add(b)
        if b == 1:
            s1.add(a)
        if a == N:
            sn.add(b)
        if b == N:
            sn.add(a)
    return bool(s1 & sn)


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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
##1からきている&&Nに行ける

road = [0]*N

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

    if a == 1:
        road[b-1] += 1
    elif b == N:
        road[a-1] += 1

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
S = set()
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    S.add((a, b))

for i in range(1, n-1):
    if (0, i) in S and (i, n-1) in S:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N_shima, M_fune = map(int, input().split())

shima_1 = []
shima_N = []

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

    if (a == 1):
        shima_1.append(b)
    elif (a == N_shima):
        shima_N.append(b)
    if (b == 1):
        shima_1.append(a)
    elif (b == N_shima):
        shima_N.append(a)
    
judge = set(shima_1) & set(shima_N)

if (len(judge) >= 1):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc068/tasks/arc079_a
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


from collections import defaultdict
N, M = ints()
# グラフを作ってたかだか2回でNに行けるかを探索する(深さ優先が楽かな？)
graph = defaultdict(lambda: [])
for _ in ra(M):
    a, b = mina(*ints())
    graph[a].append(b)
    graph[b].append(a)


def dfs(now, fr, d):
    if d == 2:
        return now == N - 1
    res = False
    for to in graph[now]:
        if fr == to:
            continue
        res = res or dfs(to, now, d + 1)
    return res


print('POSSIBLE' if dfs(0, -1, 0) else 'IMPOSSIBLE')

Submission status: Accepted

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

dic = {1:set(), N:set()}

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

for i in dic[1]:
  if i in dic[N]:
    print("POSSIBLE")
    exit()
    
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import queue
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

def main():
    N,M = [int(x) for x in input().split()]
    C = defaultdict(list)
    for _ in range(M):
        a,b = [int(x) for x in input().split()]
        C[a-1].append(b-1)
    
    # bfs
    q = queue.Queue()
    # ステップ数
    V = [0]*N
    V[0] = 0
    # 始点
    s = 0
    while True:
        # print(s)
        for u in C[s]:
            # print(u,V[u])
            if V[u] == 0:
                q.put(u)
                V[u] = V[s]+1 # ステップ数
        if q.empty() or V[N-1] > 0:
            break
        s = q.get()
    # print(V[N-1])
    
    if 0 < V[N-1] and V[N-1] <= 2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
        
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)]


def binary_search(num_list, target):
    # 「値が何番目にあるか」を確認するための変数
    ans_counter = 0
    while True:
        # 配列の中心にある値を取り出す
        middle = num_list[len(num_list) // 2]
        # 配列の左側
        left = num_list[:len(num_list) // 2]
        # 配列の右側
        right = num_list[len(num_list) // 2:]
        # 中心の値が探索値と一致したら探索終了(探索値発見)
        if middle == target:
            ans_counter += len(left) + 1
            print("{}は{}番目にありました。".format(target, ans_counter))
            break
        # 値が最後の1個になっても一致しなかったら探索終了(探索値不存在1)
        # 左の最大値 < 探索値 < 右の最小値となった場合探索終了(探索値不存在2)
        elif len(num_list) == 1 and num_list[0] != target\
                or left[-1] < target < right[0]:
            print("{}はありませんでした。".format(target))
            break
        # 左の最大値より探索値が小さい場合、探索範囲を左側に絞る
        elif target <= left[-1]:
            num_list = left
        # 右の最小値より探索値が大きい場合、探索範囲を右側に絞る
        elif right[0] < target:
            ans_counter += len(left)
            num_list = right


first_hune = [False for _ in range(n + 1)]
second_hune = [False for _ in range(n + 1)]

AB.sort(key=lambda x: [x[0], x[1]])
totyu = []
for a, b in AB:
    if a == 1:
        first_hune[b] = True
    if b == n:
        if first_hune[a] is True:
            print('POSSIBLE')
            exit()


print('IMPOSSIBLE')

Submission status: Accepted

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

near = [set([]) for _ in range(n)]
for a, b in ab:
    near[a - 1].add(b - 1)
    near[b - 1].add(a - 1)

for i in near[0]:
    if i in near[n - 1]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

dic={}

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

for i in range(m):
    a,b=ab[i]
    if a==1:
        dic[b]=1

# print(dic)
for i in range(m):
    a,b=ab[i]
    if b==n and a in dic:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

# bfs
def bfs(v):
   dist = [-1] * n
   dist[v] = 0
   visit = [v]
   c = 1
   while visit:
      next = []
      for i in visit:
         for j in edges[i]:
            if dist[j] == -1:
               dist[j] = c
               next.append(j)
      visit = next
      c += 1
      if c > 2:
         break

   return dist

dist = bfs(0)
if dist[-1] == -1:
   print('IMPOSSIBLE')
else:
   print('POSSIBLE')

Submission status: Accepted

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

res = []
for elem in dic[1]:
  res += dic[elem]
if n in res:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
W = V[1]
z = []
for x in W:
    z.append(V[x])
s = 0
for q in z:
    if n in q:
        s = 1
        break
if s == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
buf = sys.stdin.buffer

n, m = map(int, buf.readline().split())
AB = map(int, buf.read().split())

reachable_from_start = set()
reachable_to_goal = set()
for a, b in zip(AB,AB):
    if a == 1:
        reachable_from_start.add(b)
    if b == n:
        reachable_to_goal.add(a)

possible = reachable_from_start & reachable_to_goal
if possible or n in reachable_from_start:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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


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

edges = [set() for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].add(to-1)

first = list(edges[0])

possible = False
while first:
    island = first.pop()
    if n-1 in edges[island]:
        possible = True
        break

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

Submission status: Accepted

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, m = LI()
a = []
b = []
for _ in range(m):
    ai, bi = LI()
    a.append(ai)
    b.append(bi)

b1 = set(bi for ai, bi in zip(a, b) if ai == 1)
an = set(ai for ai, bi in zip(a, b) if bi == n)

s = b1 & an
ans = 'POSSIBLE' if len(s) > 0 else 'IMPOSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
b=set()
c=set()
for l in a:
  if l[0]==1:
    b.add(l[1])
  elif l[1]==n:
    c.add(l[0])
for x in b:
  if x in c:
    print("POSSIBLE")
    sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
from1=set([])
fromN=set([])
# a<b
for _ in range(M):
  a, b=map(int, input().split())
  if a==1:
    from1.add(b)
  if b==N:
    fromN.add(a)
while from1:
  if from1.pop() in fromN:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
route = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    route[a-1].append(b)
    
for i in route[0]:
    if len(route) != 1:
        for j in route[i-1]:
            if j == N:
                print('POSSIBLE')
                sys.exit()
    else:
        if i == N:
            print('POSSIBLE')
            sys.exit()
                
print('IMPOSSIBLE')

Submission status: Accepted

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

a = [0]*N
b = [0]*N

for i in range(M):
    if ll[i][0] == 1:
        a[ll[i][1]-1] += 1
    if ll[i][1] == N:
        b[ll[i][0]-1] += 1

for i in range(N):
    if a[i] != 0 and b[i] != 0:
        print("POSSIBLE")
        exit()
    else:
        pass
print("IMPOSSIBLE")

Submission status: Accepted

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

l1=[0]*n
ln=[0]*n
for i in range(m):
    if ab[i][0]==1:
        l1[ab[i][1]-1]+=1
    if ab[i][1]==n:
        ln[ab[i][0]-1]+=1
    #print(l1,ln)
for i in range(n):
    if l1[i]!=0 and ln[i]!=0:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

G = [deque([]) 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)

time = 0

for i in range(len(G[0])):
    if (N-1) in G[G[0][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)]
f=set([ft[1] for ft in ab if ft[0]==1])
t=set([ft[0] for ft in ab if ft[1]==n])
if f&t: print("POSSIBLE")
else: print("IMPOSSIBLE")

Submission status: Accepted

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

if len(A[0])+len(A[-1]) != len(set(A[0]+A[-1])):
        print("POSSIBLE")
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(set)

    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].add(b)
        edge[b].add(a)

    for u in edge[1]:
        if n in edge[u]:
            print("POSSIBLE")
            sys.exit()

    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for dst in graph[0]:
    if n-1 in graph[dst]:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  li[x-1].append(y-1)
  li[y-1].append(x-1)
an=[]
for i in li[0]:
  an+=li[i]
if n-1 in an:
  print('POSSIBLE')
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(lambda x: int(x)-1, input().split())
  G[a].append(b)

for v in G[0]:
  if N-1 in G[v]:
    print("POSSIBLE")
    exit()
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(lambda x: int(x)-1, input().split())
  G[a].append(b)

for v in G[0]:
  for nv in G[v]:
    if nv == N-1:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

for first in g[0]:
    if n-1 in g[first]:
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
B = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    A.append(b)
  if b == N:
    B.append(a)
C = list(set(A) & set(B))
ans = 'IMPOSSIBLE'
if len(C) > 0:
  ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
f = {}
s = {}


for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f[b] = 1
        if b in s:
            print("POSSIBLE")
            exit()
    if b == n:
        s[a] = 1
        if a in f:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
f = [0]*200020
s = [0]*200020


for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        f[max(a, b)] = 1
        if s[max(a, b)] == 1:
            print("POSSIBLE")
            exit()
    if a == n or b == n:
        s[min(a, b)] = 1
        if f[min(a, b)] == 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

if x&y:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

l = list()
la = [0] * (n+1)
ln = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        la[b] = 1
    elif b == 1:
        la[a] = 1
    if a == n:
        ln[b] = 1
    elif b == n:
        ln[a] = 1

for i in range(n+1):
    if la[i]*ln[i] == 1:
        print("POSSIBLE") 
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import heapq

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

roots = [[] for _ in range(n)]

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

def dijkstra(edges, s):
    hq = []
    d = [-1] * n
    d[s] = 0
    heapq.heappush(hq, (0, s))
    while hq:
        d1, p = heapq.heappop(hq)
        for i in edges[p]:
            if d[i] == -1 or d[i] > d1 + 1:
                d[i] = d1 + 1
                heapq.heappush(hq, (d1+1, i))
    return d

d = dijkstra(roots, 0)

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

Submission status: Accepted

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

li1 = [False] * n
lin = [False] * n

for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        li1[b-1] = True
    elif b == n:
        lin[a-1] = True

for i in range(n):
    if li1[i] and lin[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

li1 = []
lin = []

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

li1.sort()
lin.sort()

tmp = 0

if not len(lin):
    print('IMPOSSIBLE')
    exit()

for i in li1:
    while i > lin[tmp]:
        tmp += 1
        if tmp == len(lin):
            print('IMPOSSIBLE')
            exit()
    if i == lin[tmp]:
        print('POSSIBLE')
        exit()


print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque

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

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[]for i in range(N+1)]
deq=deque()

for i in range(M):
    A,B=map(int,input().split())
    S[A].append(B)
    S[B].append(A)
    
#print(S)    
lenN=len(S[N])
for i in range(lenN):
    v=S[N][i]
    #print(v)
    #print(S[v])
    
    if 1 in S[v]: 
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A, B = [0]*n, [0]*n
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] += 1
    if b == n:
        B[a-1] += 1
if sum(B) == 0:
    print(ans)
    exit()
else:
    for i in range(n):
        if A[i] == 1 and B[i] == 1:
            ans = 'POSSIBLE'
            break
    print(ans)

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = []
new = []
for i in range(m):
    if ls[i][0] == 1:
        di.append(ls[i][1])
    if ls[i][1] == n:
        new.append(ls[i][0])
f = list(set(di) & set(new))
if len(f) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

l = [[] for _ in range(n+1)]

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

if len(l[n]):
    for x in l[n]:
        if l[x].count(0):
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())

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

q = deque()
q.append((0,0))
while q:
    now,cnt = q.popleft()
    if now==n-1 and cnt==2:
        print('POSSIBLE')
        exit()
    if cnt>=2:
        continue
    for index in Map[now]:
        q.append((index,cnt+1))
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[[] for i in range(N)]
for j in range(M):
    a,b=map(int,input().split())
    AB[a-1].append(b)
    AB[b-1].append(a)
for ab in AB:
    if 1 in ab and N in ab:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[0]*n
B=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        A[b-1]=1
    if b==n:
        B[a-1]=1

ans="IMPOSSIBLE"
for i in range(n):
    if A[i]==1 and B[i]==1:
        ans="POSSIBLE"
        break
print(ans)

Submission status: Accepted

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

from collections import deque 

def bfs(u, g): #uからの最短経路を求める
    u-=1
    queue = deque([u])
    d=[-1]*n
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is -1:
                d[i]=d[v]+1
                queue.append(i)
    return d

d = bfs(1,g) #dは頂点sからの最短経路
if d[-1]==2:
    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)]

graph = [[] for _ in range(n)]
for v in ab:
    graph[v[0]-1].append(v[1]-1)
    graph[v[1]-1].append(v[0]-1)
# print(graph)

from collections import deque

queue = deque([0])
d = [10**6] * n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in graph[v]:
        if d[i]==10**6:
            d[i] = d[v] + 1
            queue.append(i)
# print(d)

print('POSSIBLE' if d[n-1]<=2 else 'IMPOSSIBLE')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    q = deque([0])
    seen = [-1] * n
    seen[0] = 0

    while q:
        u = q.popleft()

        for v in g[u]:
            if seen[v] == -1 or seen[v] > seen[u] + 1:
                seen[v] = seen[u] + 1
                q.append(v)

    if seen[n - 1] == 2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
set_a = set()
set_b = set()
AB = [list(int(x) for x in input().split()) for _ in range(m)]


for a,b in AB:
  if a > b:
    a,b = b,a
  
  if a == 1:
    set_a.add(b)
  if b == n:
    set_b.add(a)

se = set_a & set_b
print('POSSIBLE' if se else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    s=set(G[1])
    ans=False
    while len(s)>0:
        now=s.pop()
        for nex in G[now]:
            if nex==n:
                ans=True
                break

    print("POSSIBLE" if ans else "IMPOSSIBLE")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    #bfs
    q=deque([tuple((1,0))])
    flags=[False]*(n+1)
    flags[1]=True
    ans=False
    while len(q)>0:
        now,d=q.popleft()
        if now==n:
            if d==2:
                ans=True
                break
        for nex in G[now]:
            if flags[nex]==False:
                flags[nex]=True
                q.append(tuple((nex,d+1)))

    print("POSSIBLE" if ans else "IMPOSSIBLE")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    N, M = map(int, input().split()) # 頂点の数、辺の数
    edge = [[] for i in range(2)] # rangeに頂点の数。繋がっている頂点を投入するリスト
    for i in range(M): # rangeに辺の数
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        if a==0 :
            edge[0].append(b)
        elif b==N-1:
            edge[1].append(a)
    if len(set(edge[0])&set(edge[1]))>=1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

resolve()

Submission status: Accepted

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

path = [[] for i in range(n)]

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

for j in path[0]:
  if n-1 in path[j]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

aset = set()
bset = set()

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

for i in bset:
  if i in aset:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    n, m = map(int,(input().split()))
    inlis = []
    lis_1 = []
    lis_n = []

    for _ in range(m):
        a, b = map(int, input().split())
        #print(a, b)
        if a == 1:
            lis_1.append(b)
            #print(lis_1)
        if b == n:
            lis_n.append(a)
            #print(lis_n)
    #print(lis_1, lis_n)
    set_1 = set(lis_1)
    set_n = set(lis_n)
    #print(set_1, set_n)
    if set_1 & set_n:
        #print(set_1 & set_n)
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    
if __name__ == "__main__":
    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())
AB = [list(map(int,input().split())) for _ in range(M)]

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

for a,b in AB:
  EDGE[a].append(b)
  EDGE[b].append(a)
  
def dfs(p,u,d):
  if u == N:
    return True
  
  if d == 0:
    return False
  
  ans = False
  
  for v in EDGE[u]:
    if v == u:
      continue
      
    ans |= dfs(u,v,d-1)
  
  return ans

ans = dfs(-1,1,2)

s = 'POSSIBLE' if ans else 'IMPOSSIBLE'

print(s)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
islands = [set() for i in range(n)]
for i in range(m):
    a, b = [int(i) for i in input().split()]
    islands[a-1].add(b)
    islands[b-1].add(a)
f = False
for i in islands[n-1]:
    if 1 in islands[i-1]: f = True
print("POSSIBLE" if f else "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())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
for i in range(1, n - 1):
    ma = 0
    mi = n
    for node in g[i]:
        ma = max(ma, node)
        mi = min(mi, node)
    if ma == n - 1 and mi == 0:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
islands=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    islands[a].append(b)
answer=1
for n in islands[1]:
    if N in islands[n]:
        answer=0
        print('POSSIBLE')
        break
if answer==1:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    ans = "IMPOSSIBLE"
    for v in G[0]:
        if N - 1 in G[v]:
            ans = "POSSIBLE"
            break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    ans = "IMPOSSIBLE"
    for v in G[0]:
        if N - 1 in G[v]:
            ans = "POSSIBLE"

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
AB = []
import collections
d = collections.defaultdict(list)
for i in range(m):
    a,b = map(int, input().split())
    #AB.append(ab)
    d[a].append(b)
    d[b].append(a)
for k in d.keys():
    if 1 in d[k] and n in d[k]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')