Problem:


Score : 300 points

Problem Statement

In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.

There are M kinds of regular boat services between these islands.
Each service connects two islands. The i-th service connects Island a_i and Island b_i.

Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.

Help him.

Constraints

3 ≤ N ≤ 200 000

1 ≤ M ≤ 200 000

1 ≤ a_i < b_i ≤ N

(a_i, b_i) \neq (1, N)

If i \neq j, (a_i, b_i) \neq (a_j, b_j).

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

You have to use three boat services to get to Island 4.

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

5 5
1 3
4 5
2 3
2 4
1 4

Sample Output 4

POSSIBLE

You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=list(list(map(int,input().split()))for _ in range(M))
graph=list([0]*N for _ in range(2))
for a,b in ab:
    if a==1:
        graph[0][b-1]=1
    elif b==N:
        graph[1][a-1]=1

for i,j in zip(graph[0],graph[1]):
    if i==1 and j==1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

# 1からN
se1 = set()
se2 = set()

for a,b in AB:
  if a>b:
    a,b = b,a
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2
answer = 'POSSIBLE' if se else 'IMPOSSIBLE'
print(answer)

Submission status: Accepted

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

N, M = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(M)]
m = [set() for _ in range(N)]

for l, r in L:
    l -= 1
    r -= 1
    
    m[l].add(r)
    
N -= 1
for v in m[0]:
    if N in m[v]:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

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

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

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

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
via=set()
viaa=set()
for i in range(m):
  a,b=map(int,input().split())
  if a ==1 : 
    via.add(b)
  if b ==n:
    viaa.add(a)
if via.isdisjoint(viaa):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Accepted

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

ab.sort(key = lambda x:x[0])

import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False
cnt = 0
for i in range(M):
    if ab[i][0] == 1:
        q.put(ab[i][1])
        cnt += 1
    else :break
ab2 = [[0]] * (N+1)
for j in range(i,M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
idx = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if idx < cnt:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    idx += 1
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
l=[]
m=[]
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        l.append(b)
    elif b==N:
        m.append(a)
o=set(l)&set(m)

if len(o):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

l = []
r = []
for x, y in X:
    if x == 1:
        l.append(y)
    if y == N:
        r.append(x)
        
print('POSSIBLE' if len(set(l) & set(r)) > 0 else 'IMPOSSIBLE')

Submission status: Accepted

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

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
gragh = [[] for i in range(n+1)]
for e in edge:
    gragh[e[0]].append(e[1])
    gragh[e[1]].append(e[0])
start = 1
for k in gragh[start]:
    if n in gragh[k]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  l=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l.append(b)
    elif b==1:
      l.append(a)
    elif a==n:
      l.append(b)
    elif b==n:
      l.append(a)

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

main()
# print(main())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
flag=False
for i in g[1]:
  for j in g[i]:
    if j==n:
      flag=True
if flag==True:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

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

if len(mae&ato) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

def solve():
    N, M = list(map(int, input().split()))
    """方針
    from1 := 1から行ける島番号のリスト
    canN[i] := 島iがNに行くことができるか否か
    from1の中の島bのうち、canN[b] == Trueのものがあるならば、POSSIBLE
    計算量はO(N)
    """
    from1 = []
    canN = [False] * (N+1)
    for i in range(M):
        a, b = list(map(int, input().split()))
        if a == 1:
            from1.append(b)
        elif b == N:
            canN[a] = True
    
    for b in from1:
        if canN[b]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")
        

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

def solve():
    N, M = list(map(int, input().split()))
    """
    from1 := 1から行ける島番号のリスト
    canN[i] := 島iがNに行くことができるか否か
    from1とtoNの両方に同じ島番号が存在するとき、POSSIBLE
    """
    from1 = []
    canN = [False] * (N+1)
    for i in range(M):
        a, b = list(map(int, input().split()))
        if a == 1:
            from1.append(b)
        elif b == N:
            canN[a] = True
    
    for b in from1:
        if canN[b]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")
        

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

if (any((b in AtN) for b in Bf1)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ship = [[int(i) for i in input().split()] for i in range(m)]
mid_first=[]    # 1本目の定期便の目的地
mid_last=[]     # 2本目の定期便の目的地

for s,e in ship:
    if s==1:
        mid_first.append(e)
    if e==n:
        mid_last.append(s)
print("POSSIBLE" if len(set(mid_first) & set(mid_last))>0 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lst_1_to_i = [False] * N
lst_i_to_N = [False] * N
ans = "IMPOSSIBLE"


for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        lst_1_to_i[b] = True
    if b == N:
        lst_i_to_N[a] = True


for x, y in zip(lst_1_to_i, lst_i_to_N):
    if x and y:
        ans = "POSSIBLE"


print(ans)

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
dict={1:[]}
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    if(a==1):
        dict[1].append(b)
    elif(b==N):
        dict[a]=b
flag = False
for i in dict[1]:
    if(i in dict):
        flag = True
        break
if(flag):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



def main():
  N,M = map(int, input().split())
  route = [0 for _ in range(N+1)]

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

  if max(route) >= 2:
    return True
  else:
    return False


if __name__ == "__main__":
  if main():
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
a=[]
b={}
n,m=map(int,input().split())
for _ in range(m):
	i,j=map(int,input().split())
	if i==1:
		a.append(j)
	elif j==n:
		b[i]=1
for i in a:
	if i in b:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Submission status: Accepted

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

goal, 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==goal:
    sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ship = {i:False for i in range(1, n+1)}
bl = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship[b] = True
    elif b == n:
        bl.append(a)

for i in bl:
    if ship[i] == True:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

for i in ship[1]:
    if n in ship[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

S, G = [False] * N, [False] * N
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S[b - 1] = True
    if b == N:
        G[a - 1] = True

if any(s and g for s, g in zip(S, G)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

S, G = set(), set()
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S.add(b)
    if b == N:
        G.add(a)

if len(S & G) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

S, G = set(), set()
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S.add(b)
    if b == N:
        G.add(a)

if any(s in G for s in S):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

flag = False

for i in range(len(link[0])):
    for j in link[link[0][i]]:
        if j == N-1:
            flag = True

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

Submission status: Accepted

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

Submission status: Accepted

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

f = set()
s = set()

for a, b in AB:
	if a == 1 or b == 1:
		f |= {a + b - 1}
	if a == N or b == N:
		s |= {a + b - N}
print(["POSSIBLE", "IMPOSSIBLE"][not(f & s)])

Submission status: Accepted

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

for i in range(N):
    if a[i] * b[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v,depth):
    # ノードに訪れた
    visited[v] = 1
    if depth == 2:
        return
    for a, b in sides:
        if v == a-1:
            depth += 1
            dfs(b-1, depth)
            depth -= 1

n, m = MI()
a, b = set(), set()
for i in range(m):
    x, y = MI()
    if x == 1:
        a.add(y)
    if y == n:
        b.add(x)

print("POSSIBLE" if a&b else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
# import statistics
import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v,depth):
    # ノードに訪れた
    visited[v] = 1
    if depth == 2:
        return
    for a, b in sides:
        if v == a-1:
            depth += 1
            dfs(b-1, depth)
            depth -= 1

n, m = MI()
sides = [LI() for _ in range(m)]
islands = [[0] * 2 for _ in range(n)]

for a, b in sides:
    if a-1 == 0:
        islands[b-1][0] = 1
    if b-1 == n-1:
        islands[a-1][1] = 1

for a, b in islands:
    if a == b == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:


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

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

    return n, m, ships


def submit():
    n, m, ships = read_input()

    links = {i: [] for i in range(1, n+1)}

    for ship in ships:
        links[ship[0]].append(ship[1])
        links[ship[1]].append(ship[0])

    set1 = set(links[1])
    set2 = set(links[n])

    if set1.intersection(set2):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')



if __name__ == '__main__':
    submit()

Submission status: Accepted

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

S = []
E = []

for i in range(M):
  if ab[i][0] == 1:
    S.append(ab[i][1])
  if ab[i][1] == N:
    E.append(ab[i][0])

if set(S) & set(E):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    s, n = map(int, input().split())
    if s == 1:
        edge1.append(n)
    elif n == N:
        edgeN.append(s)
if len(set(edge1) & set(edgeN)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def c_cat_snuke_and_a_voyage(N, M, I):
    node1 = [False] * N  # 島1と島iに辺があるならTrue, なければFalse
    node2 = [False] * N  # 島iと島Nに辺があるならTrue, なければFalse
    for a, b in I:
        if a == 1:  # 出発地が島1なら
            node1[b] = True
        elif b == N:  # 目的地が島Nなら
            node2[a] = True
    return 'POSSIBLE' if any([p and q for p, q in zip(node1, node2)]) else 'IMPOSSIBLE'

N, M = [int(i) for i in input().split()]
I = [[int(i) for i in input().split()] for j in range(M)]
print(c_cat_snuke_and_a_voyage(N, M, I))

Submission status: Accepted

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

fr = []
to = []

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

fr.sort()
to.sort()

searched = 0
for i in range(len(fr)):
    while searched <= len(to) - 1 and to[searched] <= fr[i]:
        if to[searched] == fr[i]:
            print('POSSIBLE')
            exit()
        searched += 1


print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from sys import exit, stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
s1 = set()
sn = set()
for _ in range(M):
    a,b = [int(_) for _ in stdin.readline().rstrip().split()]
    if a==1:
        s1.add(b)
    elif b==N:
        sn.add(a)
for x in s1:
    if x in sn:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


N,M = map(int,input().split())
a = []
for i in range(M):
    x,y = map(int,input().split())
    a.append([x,y])

ans = False
routes_s = []
routes_g = []

for ai in range(len(a)):
    if 1 in a[ai]:
        inx = a[ai].index(1)
        routes_s.append(a[ai][inx-1])
    if N in a[ai]:
        inx = a[ai].index(N)
        routes_g.append(a[ai][inx-1])

# print(routes)
if 1 in routes_g or N in routes_s:
    print("POSSIBLE")
    exit()

s_reach = list(set(routes_s))
g_reach = list(set(routes_g))
sg_reach = list(set(g_reach+s_reach))

if len(s_reach)+len(g_reach) != len(sg_reach):
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

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

flg = 0
for i in voyage[0]:
    if N-1 in voyage[i]:
        flg = 1

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

Submission status: Accepted

Solution code:
from functools import reduce
from collections import defaultdict
from collections import deque
import math

def btf(i,d,N):
    q = deque()
    q.append(i)
    dist = [-1]*N
    dist[i] = 0
    i = 1
    while q:
        l = len(q)
        for j in range(l):
            next_node = q.popleft()
            for succ in d[next_node]:
                if dist[succ] == -1:
                    dist[succ] = i
                    q.append(succ)
        i +=1
    return dist

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N,M = (int(_) for _ in input().split())
    d = defaultdict(list)
    
    for i in range(M):
        s1,s2 = (int(_) for _ in input().split())
        d[s1-1].append(s2-1)
        d[s2-1].append(s1-1)

    dist = btf(0,d,N)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[[]for i in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  l[a]+=[b]
  l[b]+=[a]
k=0
for i in l[0]:
  if n-1 in l[i]:
    k=1
if k:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc068/tasks/arc079_a

import itertools
import collections
import bisect

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

    src = {}
    A = []
    B = []
    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

        if a == 1:
            src[b] = 1

    for i in range(M):
        if A[i] in src and B[i] == N:
            print("POSSIBLE")
            exit()

    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
one=[0 for i in range(n)]
ans = "IMPOSSIBLE"
for i in a:
  if i[0] == 1:
    if one[i[1]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[1]] = 1
  elif i[1] == n:
    if one[i[0]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[0]] = 1
print(ans)

Submission status: Accepted

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

print("POSSIBLE" if len({b_i for a_i, b_i in zip(a, b) if a_i == 1} & {a_i for a_i, b_i in zip(a, b) if b_i == n}) > 0 else "IMPOSSIBLE")

Submission status: Accepted

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

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1 or a==n:s.append(b)
    elif b==1 or b==n:s.append(a)
ls=len(s)
s=list(set(s))
if ls==len(s):print("IMPOSSIBLE")
else:print("POSSIBLE")

Submission status: Accepted

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while x < m and a[x][0]== 1:
    li_a.append(a[x][1])
    x += 1

a.sort(reverse=True, key=lambda x: x[1])

x = 0
li_b = []

while x < m and a[x][1] == n:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")

Submission status: Accepted

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

A = [False] * N
B = [False] * N
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] = True
    if b == N:
        B[a-1] = True

flag = False
for i in range(N):
    if A[i] and B[i]:
        flag = True
        break

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
route = defaultdict(lambda: False)
for i in range(M):
    ai, bi = map(int, input().split())
    route[(ai, bi)] = True

possible = False
for i in range(2, N):
    if route[(1, i)] and route[(i, N)]:
        possible = True
print('POSSIBLE' if possible else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()
X,Y=[],[]
for i in range(M):
	a = LI()
	if a[0] == 1:
		X.append(a[1])
	if a[1] == N:
		Y.append(a[0])
X=set(X)
Y=set(Y)
for x in X:
	if x in Y:
		print("POSSIBLE")
		exit()
	

	
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[]
y=[]
ans='POSSIBLE'
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    elif b==n:
        y.append(a)
if len(set(x)&set(y))==0:
    ans='IMPOSSIBLE'
print(ans)

Submission status: Accepted

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

x = adj[1].intersection(adj[n])
if len(x) != 0:
    print("POSSIBLE")
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)
  elif b==n:
    B.append(a)
print("POSSIBLE" if len(set(A)&set(B))>0 else "IMPOSSIBLE")

Submission status: Accepted

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

for x in s1:
    if x in sn:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
lis = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = nm()
    lis[a].append(b)
    lis[b].append(a)
for i in range(len(lis[1])):
    l = lis[1][i]
    if n in lis[l]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
fastinput=sys.stdin.readline
N,M=map(int,fastinput().split())
first=[False]*N
second=[False]*N
for _ in range(M):
    i,j=[int(k) for k in fastinput().split()]
    if i==1:
        first[j-1]=True
    if j==N:
        second[i-1]=True
if any([(first[a] and second[a]) for a in range(N)]):
    print("POSSIBLE")
else:print("IMPOSSIBLE")

Submission status: Accepted

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

way = [0] * (n + 1)
for a, b in ab:
    if a == 1:
        way[b] += 1
    if b == 1:
        way[a] += 1
    if a == n:
        way[b] += 1
    if b == n:
        way[a] += 1
if 2 in way:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ships = [list(map(int, input().split())) for _ in range(m)]
starts = list(map(lambda x:x[1], list(filter(lambda x:x[0]==1, ships))))
goals = list(map(lambda x:x[0], list(filter(lambda x:x[1]==n, ships))))
if len(set(starts+goals)) != len(starts+goals):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#21:06
N,M=map(int,input().split())
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
first=[]
last=[]
H=[[] for i in range(N)]
for t in l:
    H[t[0]-1].append(t[1])
    H[t[1]-1].append(t[0])
#if H[0][0]==H[N-1][0]
#print(any(N in H[0]))
#for v in H[0]:
if any(N in H[v-1] for v in H[0]):
    #N is exist in first
    #1 to i to N
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split());a=[]
for i in range(m):
  aa,bb=map(int,input().split())
  if aa==1:a.append(bb)
  if bb==n:a.append(aa)
a.sort()
for i in range(len(a)-1):
  if a[i]==a[i+1]:print("POSSIBLE");exit()
print("IMPOSSIBLE")