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:
from collections import deque
n,m = map(int,input().split())

adj = [[] for i in range(n)]
dist = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
q = deque()
dist[0] = 0
q.append(0)

while len(q) > 0:
    x = q.popleft()
    
    for f in adj[x]:
        if dist[f] != -1:
            continue
        
        dist[f] = dist[x] + 1
        q.append(f)
     
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

adj = [[] for i in range(n)]
dist = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
q = queue.Queue()
dist[0] = 0
q.put(0)

while not q.empty():
    x = q.get()
    
    for f in adj[x]:
        if dist[f] != -1:
            continue
        
        dist[f] = dist[x] + 1
        q.put(f)
     
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
dum = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    dum[a-1].append(b-1)
for i in dum[0]:
    if dum[i].count(n-1) >= 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arrival=set([])
deperture=set([])
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        deperture.add(b)
    if b==n:
        arrival.add(a)

if len(arrival&deperture)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    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)
    for e in G[0]:
        if N-1 in G[e]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
# ab = [list(map(int,input().split())) for i in range(m)]
v = [[] for i in range(n+1)]
# print(v)
for i in range(m):
    a,b = map(int,input().split())
    v[a].append(b)
    v[b].append(a)
while v[1]:
    temp = v[1].pop()
    if n in v[temp]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    if (set(G[0]) & set(G[n-1])):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
    return

solve()

# T = ni()
# for _ in range(T):
#     solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
flg=0
for i in range(m):
  p,q=map(int,input().split())
  if (p==1 and q==n) or (p==n and q==1):
    flg=1
  elif p==1:
    a[q]=1
  elif q==1:
    a[p]=1
  elif p==n:
    b[q]=1
  elif q==n:
    b[p]=1
for i in range(1,n+1):
  if a[i]==1 and b[i]==1:
    flg=1
if flg==1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def answer(destination, services):
    P, M = ("POSSIBLE", "IMPOSSIBLE")
    dic = {}
    for a, b in services:
        if dic.get(a) is None:
            dic[a] = [b]
        else:
            dic[a].append(b)
        if dic.get(b) is None:
            dic[b] = [a]
        else:
            dic[b].append(a)
    if dic.get(destination) is None: return M
    arr = dic[destination]
    for i in arr:
        if 1 in dic[i]:
            return P
    return M

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

Submission status: Accepted

Solution code:
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, m = input_list()
    starts = []
    ends = []
    for _ in range(m):
        a, b = input_list()
        if a == 1:
            starts.append(b)
        elif b == n:
            ends.append(a)
    
    if set(starts) & set(ends):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

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 G[0]:
  for j in G[i]:
    if j == N-1:
      print('POSSIBLE')
      exit()
      
print('IMPOSSIBLE')

Submission status: Accepted

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

fukasa = [10 ** 18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = set([0])
kouho = 1

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					kouho += 1
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

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

fukasa = [10**18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
# import math
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
#sys.stdin = open("input.txt", "r")
#sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)


    


N,M=l()
g=[[]  for i in range(N+1)]
for i in range(M):
    a,b=l()
    g[a].append(b)
    g[b].append(a)
pos=0
for j in g[1]:
    if(N in g[j]):
        pos=1
        break
if(N in g[1] or pos):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

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

    edge[a].append(b)
    edge[b].append(a)


from collections import deque

d = deque([0])

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

while d:
    v = d.popleft()

    for w in edge[v]:
        if dist[w]==-1:
            dist[w]=dist[v]+1
            d.append(w)

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    g = defaultdict(list)

    for n in ab:
        g[n[0]].append(n[1])

    if 1 not in g:
        print('IMPOSSIBLE')
        exit()

    for i in g[1]:
        if i not in g:
            continue
        for j in g[i]:
            if j == N:
                print('POSSIBLE')
                exit()

    print('IMPOSSIBLE')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N,M,*abf = map(int, open(0).read().split())
ab = [abf[i:i+2] for i in range(0, len(abf), 2)]

connected = [[]for _ in range(N+1)]
for u, v in ab:
    connected[u].append(v)
    connected[v].append(u)
    
d = deque([])
for x in connected[1]:
    if x == N:
        print('POSSIBLE')
        break
    else:
        d.append(x)
else:
    while d:
        temp = d.popleft()
        for x in connected[temp]:
            if x == N:
                print('POSSIBLE')
                break
        else:
            continue
        break
    else:
        print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

N, M = map(int, sys.stdin.readline().strip().split())

paths = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    paths[a].append(b)
    paths[b].append(a)

for i in paths[1]:
    for j in paths[i]:
        if j == N:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

paths = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    paths[a].append(b)
    paths[b].append(a)

q = deque([(1, 0)])
visited = set()
while q:
    p, c = q.popleft()
    if p in visited:
        continue
    visited.add(p)
    if c > 2:
        continue
    if p == N:
        print("POSSIBLE")
        sys.exit()
    for next_p in paths[p]:
        q.append((next_p, c+1))

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    n, m = map(int, readline().split())
    to = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, readline().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    INF = int(1e6) 
    dq = deque()
    dq.append(0)
    dist = [INF for _ in range(n)]
    dist[0] = 0
    while len(dq)>0: 
        v = dq.popleft()
        for nx in to[v]:
            if dist[nx] != INF:
                continue
            dq.append(nx)    
            dist[nx] = dist[v]+1
    if dist[n-1] == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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


# 島iから行ける島のリスト
reachables = defaultdict(set)
for a, b in data:
    reachables[a].add(b)
    reachables[b].add(a)

# 島1から行けるところ
reachables_from1 = reachables[1]
possible = False
for i in reachables_from1:
    if n in reachables[i]:
        possible = True
        break

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

#############
# Main Code #
#############

N, M = getNM()
dist = [set() for i in range(N)]
for i in range(M):
    a, b = getNM()
    dist[a - 1].add(b - 1)
    dist[b - 1].add(a - 1)

flag = False
for i in list(dist[0]):
    if N - 1 in dist[i]:
        flag = True
print('POSSIBLE' if flag else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from_1 = set()
to_N = set()
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    from_1.add(b)
  if b == N:
    to_N.add(a)

if len(from_1 & to_N) >= 1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
reachable_islands_from_1 = []    # (using just one boat service)
reachable_islands_from_n = []    # same

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

if len(list(set(reachable_islands_from_1) & set(reachable_islands_from_n))) == 0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
ab = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

ans = "IMPOSSIBLE"
for u in ab[1]:
    if N in ab[u]:
        ans = "POSSIBLE"
        break
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:
    sa.add(b)
  if b==n:
    sb.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
N = str(N)
AB = [input().split() for _ in range(M)]
_1B = set([ab[1] for ab in AB if ab[0] == '1'])
BN = set([ab[0] for ab in AB if ab[1] == N])
if len(_1B&BN) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

mid_from = set()
mid_to = set()

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ship = Ship(f, t)
  if ship.land_from == 0:
    mid_from.add(ship.land_to)
  if ship.land_to == N - 1:
    mid_to.add(ship.land_from)

# 最後の島が到達可能であるかを判定
if mid_from & mid_to:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
    n, m = list(map(int, input().split()))
    connect_1 = set()
    connect_n = set()
    for _ in range(m):
        a, b = list(map(int, input().split()))
        if a == 1:
            connect_1.add(b)
        elif b == n:
            connect_n.add(a)
        else:
            pass
    if connect_1.isdisjoint(connect_n):
        print('IMPOSSIBLE')
    else:
        print('POSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

st,go = set(),set()
for i in range(m):
    if 1 in L[i]:
        st.add(L[i][1])
    if n in L[i]:
        go.add(L[i][0])

if set(st)&set(go):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = [[]*n for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    L[a-1] += [b]
    L[b-1] += [a]
#print(L)
for i in L[0]:
    if n in L[i-1]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])): #交叉しているか？
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Accepted

Solution code:
#2問目
N, M = map(int, input().split())
link1 = [False for i in range(N+1)]
link2 = [False for i in range(N+1)]
flag = False
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        link1[B] = True
    elif B == N:
        link2[A] = True
for i in range(2, N):
    if link1[i] and link2[i]:
        print("POSSIBLE")
        flag = True
        break
if flag == False:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque

N,M=map(int,input().split())
graph=[[] for _ 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)

def dfs(start):
    d=[float("inf")]*N
    d[start]=0

    queue=deque([start])
    while queue:
        x=queue.popleft()
        for y in graph[x]:
            if d[y]!=float("inf"):
                continue
            d[y]=d[x]+1
            queue.append(y)
    
    return d

d=dfs(0)
if d[-1]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
edge = []
for i in range(n+1):
    edge.append([])
for i in range(m):
    a,b = map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
for i in edge[1]:
    if n in edge[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict 
V = defaultdict(list)

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * (n+1) # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in V[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

b1 = bfs(1)
if b1[n] ==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

s1 = set()
s2 = set()
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s1.add(b)
    elif b == 1:
        s1.add(a)
    elif a == n:
        s2.add(b)
    elif b == n:
        s2.add(a)

if s1.isdisjoint(s2):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
import bisect


def main():
    N, M = list(map(int, input().split(' ')))
    from_1 = list()
    to_n = list()
    for _ in range(M):
        a, b = list(map(int, input().split(' ')))
        if a == 1:
            from_1.append(b)
        elif b == N:
            to_n.append(a)
    from_1.sort()
    for via in to_n:
        index = bisect.bisect_left(from_1, via)
        if index < len(from_1) and from_1[index] == via:
            print('POSSIBLE')
            return
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
E1=set()
EN=set()
for i in range(M):
    x,y=map(int,input().split())
    if x==1 or y==1:
        E1.add(x)
        E1.add(y)

    if x==N or y==N:
        EN.add(x)
        EN.add(y)

if E1 & EN!=set():
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        if dist[v] >1:
            continue
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

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

Submission status: Accepted

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

N, M = map(int, input().split())
B = {}
for i in range(1, N+1):
    B[i] = []

for i in range(M):
    a, b = map(int, input().split())
    if b == N or a == 1:
        B[a].append(b)
for sima in B[1]:
    if N in B[sima]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

flag = False
for i in d[1]:
    if i in d.keys():
        for j in d[i]:
            if j == N:
                flag = True
                break
        if flag:
            break
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
island_1 = []
island_n = []
ans = "IMPOSSIBLE"

for i in range(m):
    AB = sorted(map(int,input().split()))
    
    if AB[0] == 1:
        island_1.append(AB[1])
        
    if AB[1] == n:
        island_n.append(AB[0])
        
island_1 = set(island_1)
island_n = set(island_n)
        
if len(island_1&island_n) > 0:
    ans = "POSSIBLE"
    
print(ans)

Submission status: Accepted

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

first = []
second = []
for a, b in L:
    if a == 1:
        first.append(b)
    if b == N:
        second.append(a)
flg = len(set(first) & set(second))
print('POSSIBLE' if flg else 'IMPOSSIBLE')

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n = n//a
    count += 1
  if a**count == n:
    return count
  else:
    return count+1

#############
# Main Code #
#############

N,M = IL()

graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)

ans = "IMPOSSIBLE"  
for i in graph[0]:
  for j in graph[i]:
    if j == N-1:
      print("POSSIBLE")
      E()
P(ans)

Submission status: Accepted

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

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

if len(set(from_1) & set(to_n)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M= list(map(int,input().split()))
import sys
A=set()
B=set()
l=[i.rstrip().split() for i in sys.stdin.readlines()]
for i,j in l:
   if i == "1":
      A.add(j)
   if j == str(N):
      B.add(i)
if len(A&B) > 0:
   print("POSSIBLE")
else:
   print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc068/tasks/arc079_a
from collections import deque
n, m = map(int, input().split())

graph = [[] for _ 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)


def bfs(graph, start, n):
    visited = [False] * n
    visited[start] = True
    que = deque([start])
    cost = [float('inf')] * n
    cost[start] = 0
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = True
                cost[n] = cost[node] + 1
                que.append(n)
    return cost

cost = bfs(graph, 0, n)
if cost[-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = {}
for i in range(m):
    if L[i][0] not in d:
        d[L[i][0]] = [L[i][1]]
    else:
        d[L[i][0]].append(L[i][1])
for j in d[1]:
    if j in d and n in d[j]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
dist = [0] * (n + 1)
dist[1] = 0
curr = 0

while q and curr <= 2:
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)
        dist[a] = dist[node] + 1

    curr = dist[a]

print("POSSIBLE" if dist[n] == 1 or dist[n] == 2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

contact = defaultdict(list)

for a, b in ab:
	contact[a-1].append(b-1)
	contact[b-1].append(a-1)

#print(contact)

for x in contact[0]:
	if N-1 in contact[x]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")