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 defaultdict
n, m = map(int, input().split())
bridges = [list(map(int, input().split())) for _ in range(m)]
first_bridge = []
second_bridge = []
bri_dict = defaultdict(list)
for bridge in bridges:
  bri_dict[bridge[0]].append(bridge[1])
  bri_dict[bridge[1]].append(bridge[0])
for bridge in bridges:
  if bridge[1] == n:
    second_bridge.append(bridge[0])

flag = False
for island in second_bridge:
  if 1 in bri_dict[island]:
    flag = True
  
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(m)]
p=[]
q=[]
for i in l:
    if i[0]==1:
        p.append(i[1])
    if i[1]==n:
        q.append(i[0])
if len(set(p)&set(q))!=0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
A = set()
B = set()

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

    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if len(A & B):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

def Dijkstra(N, edges, s):
    from heapq import heappush, heappop, heapify
    dist = [10**18 for _ in range(N)]
    dist[s], h = 0, [[0, s]]
    while (len(h)):
        p = heappop(h)
        d, v = p[0], p[1]
        if d > dist[v]:
            continue
        for i in range(len(edges[v])):
            u = edges[v][i]
            if d + 1 < dist[u]:
                dist[u] = d + 1
                heappush(h, [dist[u], u])
    return dist

N, M = map(int, input().split())
es = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    es[a].append(b)
    es[b].append(a)
dist = Dijkstra(N, es, 0)
if dist[N - 1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
judge = 0 #0:不可,1:可

if(M >= 2):
 #リスト 島1~a間に定期便あり:1,なし:0
 island1 = [0]*N
 #リスト 島b~N間に定期便あり:1,なし:0
 islandN = [0]*N

 for i in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  if(a == 0): island1[b] = 1
  if(b == 0): island1[a] = 1 
  if(a == N-1): islandN[b] = 1
  if(b == N-1): islandN[a] = 1
    
 for i in range(len(island1)):
  if((island1[i] == 1)and(islandN[i] == 1)):
    judge = 1
    break
    
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
def input():
    return sys.stdin.readline()
n,m=map(int,input().split())
a=[0]*(m+1)
b=[0]*(m+1)
c=[0]*(n+1)
f1=[]
f2=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        c[b[i]]=1

ans='IMPOSSIBLE'
for i in range(m):
    if b[i]==n:
        if c[a[i]]==1:
            ans='POSSIBLE'
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
INF = float("inf")


N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
dist = [INF]*(N)
for i in range(M):
    if ab[i][0] == 1:
        dist[ab[i][1]-1] = 1
for i in range(M):
    if ab[i][1] == N:
        if dist[ab[i][0]-1] <= 1:
            print("POSSIBLE")
            exit()
        else:
            continue
print("IMPOSSIBLE")

Submission status: Accepted

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

li_route = list()

for i in range(m):
    li_route.append(list(map(int, input().split())))

starts = set(l[1] for l in li_route if l[0] == 1)

ends = set(l[0] for l in li_route if l[1] == n)

if len(starts.intersection(ends)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

    q = deque()
    for a in A[1]:
        q.append(a)

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
possible=[]
possible2=[]
for i in l:
  if i[0]==1:
    possible.append(i[1])
for i in l:
  if i[1]==n:
    possible2.append(i[0])
if len(set(possible)&set(possible2))>0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, (input().split()))
L1 = [0 for i in range(N)]
L2 = [0 for j in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        L1[b - 1] = 1
    elif b == N:
        L2[a - 1] = 1
for i in range(N):
    if L1[i] == L2[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
input = open(0).read

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

# abm は ai と bi の tuple を持つ list
*abm, = zip(l[::2], l[1::2])


def f(i):
    # 1 は tuple 1番目の要素 なので 2番目の要素
    # N は tuple 2番目の要素 なので 1番目の要素
    return set(abi[i < 2] for abi in abm if i in abi)


def main():
    print("POSSIBLE" if f(1) & f(n) else "IMPOSSIBLE")


main()

Submission status: Accepted

Solution code:
from sys import stdin

lines = stdin.readlines

l = [[int(i) - 1 for i in line.split()] for line in lines()]

N, M = l[0][0] + 1, l[0][1] + 1


def main():
    f = [False] * N
    t = [False] * N

    for a, b in l[1:]:
        if a == 0:
            f[b] = True
        elif b == N - 1:
            t[a] = True

    for a, b in zip(f, t):
        if a and b:
            print("POSSIBLE")
            return
    else:
        print("IMPOSSIBLE")

    return


main()

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
A = [0 for i in range(200000+1)]
B = [0 for i in range(200000+1)]
ans = 'IMPOSSIBLE'

for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1:
        A[b] = 1
        if A[b] and B[b]:
            ans = 'POSSIBLE'
            break
    elif b == N:
        B[a] = 1
        if A[a] and B[a]:
            ans = 'POSSIBLE'
            break
print(ans)

Submission status: Accepted

Solution code:
def cat_snuke_and_a_voyage(N: int, M: int, ships: list)->bool:
    passable = [(False, False)] * (N-2)
    for a, b in ships:
        if a == 1:
            _, bN = passable[b-2]
            passable[b-2] = (True, bN)
            if bN:
                return True
        elif b == N:
            a1, _ = passable[a-2]
            passable[a-2] = (a1, True)
            if a1:
                return True
    return False


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    ships = [tuple(map(int, input().split())) for _ in range(M)]
    yes = cat_snuke_and_a_voyage(N, M, ships)
    print('POSSIBLE' if yes else 'IMPOSSIBLE')

Submission status: Accepted

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

set1=set()
setn=set()

for s in S:
  a=min(s)
  b=max(s)
  if a==1 and b==N:
    print('POSSIBLE')
    break
  elif a==1:
    set1.add(b)
  elif b==N:
    setn.add(a)
  else:
    continue
else:
  if (set1 & setn):
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
I=lambda:map(int,input().split())
N,M=I()
d={i+1:0 for i in range(N)}
for _ in[0]*M:
  a,b=I()
  if a in [1,N]:d[b]+=1
  if b in [1,N]:d[a]+=1
#print(d)
for i in range(2,N):
  if d[i]==2:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
l_1 = [False] * n
l_n = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l_1[b] = True
    elif b == n:
        l_n[a] = True
for i in range(n):
    if l_1[i] == True and l_n[i] == True:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
one = []
nnn = []
for i in range(M):
    ai,bi = map(int,input().split())
    if ai == 1:
        one.append(bi)
    if bi == N:
        nnn.append(ai)
def bs_left(l, target): # l=sorted, target以上の値をもつ要素のうち一番左のindexを返す
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if l[mid] < target:
            low = mid+1
        else:
            high = mid
    if low == len(l):
        return -1
    return low
flag = False
if len(one) == 0 or len(nnn) == 0:
    pass
else:
    nnn.sort()
    for i in range(len(one)):
        if nnn[bs_left(nnn,one[i])] == one[i]:
            flag = True
            break

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=[]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b])
    
I=[e for i,e in X if i==1]

E=[i for i,e in X if e==n]



if set(I)&set(E)!=set():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
d={1:set(),N:set()}
for i in range(M):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a]|={b,}
    if b in d.keys():
        d[b]|={a,}
if len(d[1]&d[N])>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
start=set()
goal=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        start|={b,}
    if a==N:
        goal|={b,}
    if b==1:
        start|={a,}
    if b==N:
        goal|={a,}
if len(start&goal)>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from sys import exit
N,M = [int(n) for n in input().split()]
Mat = [set() for _ in range(N)]#Nの隣接リスト
for i in range(M):
    a,b = [int(n) for n in input().split()]
    Mat[a-1].add(b-1)
    Mat[b-1].add(a-1)
N-=1
for ne in Mat[0]:
    # print(N,Mat[ne])
    if N in Mat[ne]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
island = [[int(_) for _ in input().split()] for _ in range(M)]
set1 = set()
setN = set()
flag = False

for i in island:
    if i[0] == 1:
        set1.add(i[1])
    elif i[1] == N:
        setN.add(i[0])

for i in set1:
    if i in setN:
        flag = True
        break

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
b_1 = []
a_N = []
ab = []
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        b_1.append(b)
    if b == N:
        a_N.append(a)
    ab.append((a,b))
    
if len(set(b_1) & set(a_N)) >= 1:
    print('POSSIBLE')
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/23
Solved on 2019/3/
@author: shinjisu
"""


# ABC 068 C - Cat Snuke and a Voyage
import bisect
#import numpy as np

def getInt(): return int(input())

def getIntList(): return [int(x) for x in input().split()]
# def getIntList(): return np.array(input().split(), dtype=np.longlong)

def zeros(n): return [0]*n
# def zeros(n): return np.zeros(n, dtype=np.longlong)

def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    N, M = getIntList()
    d.dmp((N, M), 'N, M')
    ship = set()
    for i in range(M):
        a, b = getIntList()
        ship.add((a, b))
    d.dmp((ship), 'ship')
    for i in range(2, N):
        if ((1, i) in ship or (i, 1) in ship) and\
             ((i, N) in ship or (N, 1) in ship):
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Accepted

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

s = [0]*n
g = [0]*n

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

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
route = [0]*(n+10)
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        route[b] += 1
    if b == n:
        route[a] += 1
if 2 in route:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b)
    E[b-1].append(a)
print("POSSIBLE")if any(N in E[v-1] for v in E[0]) else print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
a_to_b=[0]*n
for i in range(m):
    a,b=[int(j) for j in input().split()]
    if a==1:
        a_to_b[b]+=1
    if b==n:
        a_to_b[a]+=1
if 2 in a_to_b:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
if len(list(set(check_1) & set(check_N))) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

e = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    e[b] += 1
  elif(b == N):
    e[a] += 1
if(2 in e):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].add(b)
        adj[b].add(a)
    for i in range(2, N):
        if i in adj[1] and N in adj[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = [0]*N
for i in range(M):
  a,b = IL()
  if a == 1:
    if data[b]==1:
      print("POSSIBLE")
      break
    else:
      data[b]=1
  if b == N:
    if data[a]==1:
      print("POSSIBLE")
      break
    else:
      data[a]=1
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
def dijkstra():
    d[0] = 0
    q = [[0,0]]
    while q:
        dx, x = heappop(q)
        for y in v[x]:
            if d[y] > dx+1:
                d[y] = dx+1
                heappush(q,[d[y],y])
n,m = LI()
v = [[] for i in range(n)]
for i in range(m):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d = [float("inf") for i in range(n)]
dijkstra()
if d[n-1] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

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

a.sort()

k = [0 for i in range(n)]

for i in range(m):
    if a[i][0] != 1:
        break
    else:
        k[a[i][1]-1] = 1

for i in range(m):
    if k[a[i][0]-1] == 1:
        if a[i][1] == n:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
l = []
r = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        l.append(b)
    elif b == N:
        r.append(a)
s = set(l).intersection(set(r))
print("POSSIBLE" if len(s) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(m)]
c = [[] for _ in range(n+1)]
for x in l:
    c[x[0]].append(x[1])
    c[x[1]].append(x[0])
if set(c[1])&set(c[n]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    
    if solve(n, edges):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

def solve(n, edges):
    x = set(edges[1])
    y = set(edges[n])

    if x & y:
        return True
    else:
        return False

main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[[0,0] for _ in range(M)]
one=set()
n=set()
for i in range(M):
    ab[i][0],ab[i][1]=map(int,input().split())
    if ab[i][0]==1:
        one.add(ab[i][1])
    elif ab[i][1]==N:
        n.add(ab[i][0])
if one.isdisjoint(n):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    if x==1:
        a[y-1]+=1
    if y==n:
        b[x-1]+=1
ans='IMPOSSIBLE'
for i in range(n):
    if a[i]*b[i]>0:
        ans='POSSIBLE'
        break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c = []
for i in range(m):
    a,b =  map(int,input().split())
    if a == 1:
        c.append(b)
    if b == n:
        c.append(a)
        
if len(c) == len(set(c)):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

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

B = []
for i in range(M):
    if A[i][0] == 1:
        B.append(A[i][1])
    if A[i][1] == N:
        B.append(A[i][0])
        
if len(set(B)) != len(B):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N , M = map(int,input().split())
L = []
transit1 = set()
transit2 = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit1.add(x[0])
    if x[0] == 1:
        transit2.add(x[1])
if transit1 & transit2 == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
N , M = map(int,input().split())
L = []
transit1 = set()
transit2 = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit1.add(x[0])
    if x[0] == 1:
        transit2.add(x[1])
if transit1 & transit2 == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
N , M = map(int,input().split())
L = []
transit = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit.add(x[0])
for x in L:
    if x[0] == 1:
        if x[1] in transit:
            print("POSSIBLE")
            quit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	elif I[1]==N:
		C.append(I[0])
		D.append(I[1])
if len(set(B)&set(C))>0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Accepted

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

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)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
if n - 1 in edge[0]:
    print("POSSIBLE")
    exit()
else:
    for e in edge[0]:
        if n -1 in edge[e]:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

tree = [[] for i in range(n)]
for i in range(m):
  tmp_a,tmp_b = map(int,input().split())
  tree[tmp_a-1].append(tmp_b-1)
  tree[tmp_b-1].append(tmp_a-1)
def bfs():
  q = deque()
  visited =[False]*n
  visited[0]=True
  for elem in tree[0]:
    q.append([elem,1])
  while q:
    i,cnt = q.popleft()
    if i == n-1 and cnt <=2 :
      print("POSSIBLE")
      exit()
    if not visited[i]:
      visited[i] = True
      if cnt<=1:
        for elem in tree[i]:
          q.append([elem,cnt+1])

bfs()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque

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

island_map = {}
for a,b in route:
    if a not in island_map:
        island_map[a] = [b]
    else:
        island_map[a].append(b)

first_island = deque()
first_island += island_map[1]
second_island = deque()

for i in first_island:
    if i in island_map:
        second_island += island_map[i]
    else:
        pass
    for j in second_island:
        if j == N:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
k=[0]*200000
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k[tb-1]+=1
    if tb == H:
        k[ta-1]+=1
s = 0
for i in range(len(k)):
    if k[i]>=2:s=1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

d1=defaultdict(int)
d2=defaultdict(int)

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        d1[b]=1
        if d2[b]==1:
            print('POSSIBLE')
            exit()
    if b==N:
        d2[a]=1
        if d1[a]==1:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
d=defaultdict(list)
n,m=map(int,input().split())
for s in range(m):
  a,b=map(int,input().split())
  d[a].append(b)
for s in d[1]:
  if n in d[s]:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M = map(int,input().split())
dic = defaultdict(list)
for i in range(M):
    a,b = map(int,input().split())
    dic[a].append(b)
def solve(dic):
    for s in dic[1]:
        for m in dic[s]:
            if m == N:
                return True
if solve(dic): print('POSSIBLE')
else: print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
J = [False]*(N+1)
K = [False]*(N+1)
J[0] = False
K[N] = False
J[1] = False
K[1] = False
for j in range(M):
  if L[j][0] == 1:
    J[L[j][1]] = True
for k in range(M):
  if L[k][1] == N:
    K[L[k][0]] = True
flag = False
for l in range(N+1):
  if J[l] and K[l]:
    flag = True
    break
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]


from collections import defaultdict, Counter
import math
from bisect import bisect_left, bisect_right
import numpy as np

#### START
n, m= map(int,input().split())
fune = []
for _ in range(m):
    li = list(map(int,input().split()))
    if 1 in li:
        li.remove(1)
        fune.append(li[0])
    elif n in li:
        li.remove(n)
        fune.append(li[0])

if len(fune)-len(set(fune))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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


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

for v in edges[-1]:
  if 0 in edges[v]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
voy = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    voy[a-1].append(b)
alen = len(voy[0])
flag = 0
for j in range(alen):
    qu = voy[0][j]-1
    if N in voy[qu]:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def solve(N, M, ABs):
    from1 = set()
    toN = set()
    for a, b in ABs:
        a, b = min(a, b), max(a, b)
        if a == 1:
            from1.add(b)
        if b == N:
            toN.add(a)
    return "POSSIBLE" if len(from1.intersection(toN)) else "IMPOSSIBLE"

if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Submission status: Accepted

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

for i in range(m):
    if a[i][0] == "1":
        A.append(a[i][1])
    if a[i][1] == str(n):
        B.append(a[i][0])
print("POSSIBLE" if set(A) & set(B) else "IMPOSSIBLE")

Submission status: Accepted

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

    from_1 = set()
    to_N = set()
    for i in range(M):
        u, v = [int(x) for x in input().split()]

        if u == 1:
            from_1.add(v)

        if v == N:
            to_N.add(u)

    ss = from_1.intersection(to_N)
    return len(ss) != 0


def main():
    ans = solve()
    if ans:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()