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
d = defaultdict(list)
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)

# アクセスを高速にするためにsetに変換
for a in d.keys():
    d[a] = set(d[a])


def solve(n, d):
    for a in d[1]:
        if n in d[a]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


print(solve(n, d))

Submission status: Accepted

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

ans = 0
for i in first:
  if i in second:
    ans = 1
    break
if ans:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
first = [False] * n
second = [set() for _ in range(max(m,n)+1)]

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        first[b] = True
    else:
        second[a].add(b)

f = True
for i in range(1, n):
    if first[i]:
        if n in second[i]:
            f = False
            break
if f:
    print('IM', end='')
print('POSSIBLE')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m = map(int,input().split())
can_flag = 0 #if 1 possible
from_1 = []
to_n = []
for i in range(m):
    s,d = map(int,input().split())
    if s == 1: from_1.append(d)
    if d == n: to_n.append(s)
from_1.sort()
to_n.sort()
idx_from = 0
idx_to = 0
#print(from_1,to_n)
while idx_from != len(from_1) and idx_to != len(to_n):
    if from_1[idx_from] == to_n[idx_to]:
        can_flag = 1
        break
    elif from_1[idx_from] > to_n[idx_to]:
        idx_to += 1
    else: idx_from += 1
if can_flag: print("POSSIBLE")
else: print("IMPOSSIBLE")

Submission status: Accepted

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

set1=set()
set2=set()

for tmp in S:
    if tmp[0]==1:
        set1.add(tmp[1])
    if tmp[1]==N:
        set2.add(tmp[0])

if len(set1&set2) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
import sys

if sys.platform =='ios':
	sys.stdin=open('input_file.txt')
	
#+++++
n,m=list(map(int, input().split()))
aa={i:[] for i in range(1,n+1)}
for _ in range(m):
	a,b = list(map(int, input().split()))
	aa[a].append(b)
	aa[b].append(a)
for a in aa[1]:
	if n in aa[a]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
side1=set()
side2=set()
for i in range(m):
	a,b=map(int,input().split())
	if a==1:
		side1.add(b)
	elif b==n:
		side2.add(a)
print(("" if side1 & side2 else "IM")+"POSSIBLE")

Submission status: Accepted

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

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

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
f=set()
t=set()
for i in range(M):
  a,b=map(int,input().split())
  if a<2:
    f.add(b)
  if b==N:
    t.add(a)
print("IM"*(len(f&t)^1)+"POSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
f=set()
t=set()
for i in range(M):
  a,b=map(int,input().split())
  if a<2:
    f.add(b)
  elif b==N:
    t.add(a)
print(("IM","")[len(f&t)]+"POSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from1=set()
toN=set()
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    from1.add(b)
  elif b==N:
    toN.add(a)
print(("","IM")[len(from1&toN)==0]+"POSSIBLE")

Submission status: Accepted

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


ans = 'IMPOSSIBLE'
if first & second:
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

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

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

if first & second:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = []
y = []
for _ 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+y)) < len(x)+len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
import collections


input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    ab = [[] for j in range(N + 1)]
    distance = [0] * (N + 1)
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        ab[a].append(b)
        ab[b].append(a)

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

    visited = set()
    visited.add(1)

    while q:
        c, d = q.popleft()

        for n in ab[c]:
            if n not in visited:
                visited.add(n)
                q.append([n, d + 1])
                distance[n] = d + 1

    if distance[N] != 0 and distance[N] <=2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")




    
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = "IMPOSSIBLE"

for i in liners[1]:
    if i in liners and N in liners[i]:
        ans = "POSSIBLE"
        break

print(ans)

Submission status: Accepted

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        lst.append(b)
    elif b == N:
        lst.append(a)
        
lst.sort()
flg = 0

for i in range(len(lst) - 1):
    if lst[i] == lst[i + 1]:
        flg = 1
        break
        
if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if cost > 2:
                continue
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


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

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
# ABC068c
import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  # 通常の辺
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  # ダイクストラ法 O(E * logV)
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if cost > 3:
                continue
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


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

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
ablist = []
hublist1 = []
hublistN = []
work = []
for i in range(M):
    ab = tuple(map(int, input().split()))
    ablist.append(ab)
    if N in ab:
        if ab[0] == N:
            hublistN.append(ab[1])
        else:
            hublistN.append(ab[0])

    if 1 in ab:
        if ab[0] == 1:
            hublist1.append(ab[1])
        else:
            hublist1.append(ab[0])
            
work = hublist1 + hublistN
c = collections.Counter(work)
if 2 in c.values():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
# print(ablist)
# print(hublist1)
# print(hublistN)
# print(work)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
print("POSSIBLE" if any(N in G[u] for u in G[1]) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d={}#{中継地:(1 or n)}
flag=False

for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        try:
            flag=(d[b]==n)
        except:
            d[b]=1
    elif b==n:
        try:
            flag=(d[a]==1)
        except:
            d[a]=n
    if flag:
        print('POSSIBLE')
        break

if not flag:
    print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

s = set()
g = set()

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

if s & g:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 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 S(): return input()
     
def main():
    N, M = LI()
    reachable_from_1 = set()
    reachable_to_N = []
    ships = []
    for _ in range(M):
        a, b = LI()
        ships.append((a, b))
        if b == N:
            reachable_to_N.append(a)
        if a == 1:
            reachable_from_1.add(b)
    ans = False
    for n in reachable_to_N:
        if n in reachable_from_1:
            ans = True
    if ans:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M = [int(i) for i in input().split()]
nes = [0] * (N+1)
for i in range(1,N+1) :
    nes[i] = []
for i in range(M) :
    a,b = [int(i) for i in input().split()]
    nes[a].append(b)
    nes[b].append(a)
ans = "IMPOSSIBLE"
for i in nes[1] :
    for j in nes[i] :
        if j == N :
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(M)]
l_1=[]
l_n=set()
for l in A:
    if 1 in l:
        l_1.append(sum(l)-1)
for l in A:
    if N in l:
        l_n.add(sum(l)-N)
for x in l_1:
    if x in l_n:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

from collections import deque

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

queue = deque()
queue.append(1)
colors = ["white"] * (N + 1)

u = queue.popleft()
colors[u] = "black"

for edge in edges[u]:
  if colors[edge] != "black":
    queue.append(edge)

for i in range(len(queue)):
  u = queue.popleft()
  colors[u] = "black"
  for edge in edges[u]:
    if colors[edge] != "black":
      queue.append(edge)

for q in queue:
  if q == N:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

u=g[0]
for v in u:
    if n-1 in g[v]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

lst=set()
for a,b in AB:
    if b==N:
        lst.add(a)

for a,b in AB:
    if a==1:
        if b in lst:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
TO = set([])
FM = set([])
for i in range(M):
    f,t = map(int, input().split())
    if f == 1:
        TO.add(t)
    elif t == N:
        FM.add(f)
if len(TO & FM)>0:
    ans = 'POSSIBLE'
else:
    ans = 'IMPOSSIBLE'
print(ans)

Submission status: Accepted

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

s = dict()

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

    if a not in s.keys():
        s[a] = list()

    s[a].append(b)

    if b not in s.keys():
        s[b] = list()

    s[b].append(a)

ans = False
for k in s[1]:
    g = s[k]
    if n in g:
        ans = True
        break

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

Submission status: Accepted

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

s = [0]*(n+1)
t = [0]*(n+1)
for i in ab:
  if i[0] == 1:
    s[i[1]] = 1
    
for i in ab:
  if i[1] == n:
    t[i[0]] = 1

for i in range(2,n):
  if s[i] == 1 and t[i] == 1:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

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=[None]*n
for i in a:
    if i[1]==n:
        if b[i[0]-1]!=None:
            print('POSSIBLE')
            exit()
        else:
            b[i[0]-1]=True
    if i[0]==1:
        if b[i[1]-1]!=None:
            print('POSSIBLE')
            exit()
        else:
            b[i[1]-1]=True
print('IMPOSSIBLE')

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=[False]*n
for i in a:
    if i[1]==n:
        b[i[0]-1]=True
for i in a:
    if i[0]==1 and b[i[1]-1]==True :
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(m)]
s=set()
for i in a:
    if i[1]==n:
        s.add(i[0])
for i in a:
    if i[0]==1 and i[1] in s:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

flag = [0, 0]
ls1 = []
ls2 = []

for i in range(m):
    if ls[i][0] == 1 and ls[i][1] == n:
        flag[0] = 1
        break
    elif ls[i][0] == 1:
        ls1.append(ls[i][1])
    elif ls[i][1] == n:
        ls2.append(ls[i][0])

ls1_ls2 = set(ls1) & set(ls2)

if len(ls1_ls2) != 0:
    flag[1] = 1

if sum(flag) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ans = "IMPOSSIBLE"
f = dict(zip(list(range(N)),[0]*N))
s = dict(zip(list(range(N)),[0]*N))
for i in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    if a == 0:
        f[b] = 1
    if b == N-1:
        s[a] = 1
if len(f) > len(s):
    for i in range(len(s)):
        if s[i] == 1 and f[i] == 1:
            ans = "POSSIBLE"
            break
else:
    for i in range(len(f)):
        if f[i] == 1 and s[i] == 1:
            ans = "POSSIBLE"
            break
print(ans)

Submission status: Accepted

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

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

ans = False
for i in range(1,n-1):
    if li1[i] and li2[i]:
        ans = True
        break

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
from heapq import heappush, heappop

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

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

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

d = dijkstra(E, 0)

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

Submission status: Accepted

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

for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    if a == 0:
        first[b] = True
    if b == N-1:
        second[a] = True
for i,e in enumerate(first):
    if e:
        if second[i]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    if  a == 1 or b== N:
        AB.append((a,b))
set1 = set()
set2 = set()
for ab in AB:
    if ab[0] == 1:
        set1.add(ab[1])
    if ab[1] == N:
        set2.add(ab[0])
if set1 & set2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
c = []
d = []
ans = "IMPOSSIBLE"
for i in range(M):
    if ab[i][0] == 1:
        c.append(ab[i][1])
    elif ab[i][1] == N:
        d.append(ab[i][0])
e = list(set(c + d))
if len(e) < len(c)+ len(d):
    ans = "POSSIBLE"
print(ans)

Submission status: Accepted

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

start = set() #  島1から渡ることのできる島
goal = set()  #  島Nへ渡ることのできる島

for _ in range(M):
  x, y = map(int, input().split())
  if x == 1:
    start.add(y)
  elif y == N:
    goal.add(x)

if start & goal:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
E=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
for e1 in E[1]:
    for e2 in E[e1]:
        if e2==N:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from operator import itemgetter

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

l1=[i for i, x in enumerate(b) if x == N]
l2=[i for i, x in enumerate(a) if x == 1]

try:
    s1=itemgetter(*l1)(a)
except:
    s1=[]
try:
    s2=itemgetter(*l2)(b)
except:
    s2=[]

if type(s1) is int:
    tmp=s1
    s1=(tmp,)
if type(s2) is int:
    tmp=s2
    s2=(tmp,)

if len(set(s1)&set(s2))>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
  N, M, *AB = map(int, open(0).read().split())

  inter, goalable = set(), set()
  
  iterator = iter(AB)
  for a, b in zip(iterator, iterator):
    if a == 1:
      inter.add(b)
    
    if b == N: 
      goalable.add(a)
      
  flag = inter & goalable
  print("POSSIBLE" if flag else "IMPOSSIBLE")
  
if __name__ == "__main__":
    main()

Submission status: Accepted

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

  inter, goalable = set(), set()
  for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
      inter.add(b)
    
    if b == N: 
      goalable.add(a)
      
  flag = inter & goalable
  print("POSSIBLE" if flag else "IMPOSSIBLE")
  
if __name__ == "__main__":
    main()

Submission status: Accepted

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

inter, goalable = set(), set()
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    inter.add(b)
    
  if b == N: 
    goalable.add(a)
      
flag = inter & goalable
print("POSSIBLE" if flag else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


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

inter = []
goalable = defaultdict(lambda: False)
for i in range(M):
  start, end = map(int, input().split())
  if start == 1:
    inter.append(end)
  else:
    if end == N: 
      goalable[start] = True
      
for i in inter:
  if goalable[i]:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=set()
B=set()
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        B.add(b)
    if b==n:
        A.add(a)
    
if len(A&B)!=0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

for k in d1:
    if k in d2: 
        ans = "POSSIBLE"
        break
else:
    ans = "IMPOSSIBLE"

print(ans)

Submission status: Accepted

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

for i in range(m):
    if s[i][0] == 1:
        d[s[i][1]] = 1
    
for i in range(m):
    if s[i][1] == n and s[i][0] in d:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=set() #最初の候補地

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    if b[i] not in c:
      c.add(b[i])
    
for j in range(M):
  if a[j]!=1:
    if a[j] in c:
      if b[j]==N:
        print("POSSIBLE")
        break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

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

for i in x[0]:
    for j in x[i]:
        if j == n-1:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

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

if x[0] == []:
    print("IMPOSSIBLE")
    exit()

for i in x[0]:
    for j in x[i]:
        if j == n-1:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(m)]
    S=[]
    G=[]
    for l in L:
        if l[0]==1: S.append(l[1])
        if l[1]==n: G.append(l[0])
    print("POSSIBLE"if len(set(S)&set(G))>0 else "IMPOSSIBLE")
main()

Submission status: Accepted

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

ship_list1 = []
ship_list2 = []
count = 0
loop = False

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i][1])
    if ab[i][1] == n:
        ship_list2.append(ab[i][0])

if len(set(ship_list1) & set(ship_list2)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
A = [0] * M
B = [0] * M

for i in range(M):
    A[i],B[i] = map(int, input().split())
aa = []
bb = []
for i in range(M):
    if(A[i] == 1):
        aa.append(B[i])
    if(B[i] == N):
        bb.append(A[i])

aa = set(aa)
bb = set(bb)
ret = aa & bb
if (len(ret) == 0):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
x=[]
y=[]
for i in range(M):
  a, b=map(int, input().split())
  if a==1:
    x.append(b)
  if b==N:
    y.append(a)
    
nx=len(x)
ny=len(y)

if nx==0 or ny==0:
  print('IMPOSSIBLE')
  exit()

x.sort()
y.sort()
i=0
j=0
out='IMPOSSIBLE'

while i+j<nx+ny-1:
  if x[i]==y[j]:
    out='POSSIBLE'
    break
  elif x[i]>y[j]:
    j+=1
  else:
    i+=1
    
print(out)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = [[0] * 2 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        x[b - 1][0] = 1
    elif b == n:
        x[a - 1][1] = 1
if [1, 1] in x:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
import copy

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

def dfs(node, count):

    if seen[node]==True:
        return
    seen[node]=True

    if node==(N-1) and count==2:
        print("POSSIBLE")
        sys.exit()
    elif count==2:
        return
    count = count + 1
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node, count)

    return

V = []
seen = [False]*N

for i in range(N):
    V.append(set())

for i in range(M):
    *l, = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)


dfs(0, 0)

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
land = [[] for i in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    land[i - 1].append(j)
def landNumber(i,path):
    for j in range(len(land[i])):
        number=land[i][j]
        if path == 2:
            if number==N:
                print('POSSIBLE')
                exit()
            else:
                continue
        else:
            if len(land[number-1]) == 0:
                continue
            else:
                landNumber(number - 1, path + 1)
    return True

if M == 1:
    print('IMPOSSIBLE')
    exit()
if landNumber(0, 1):
    print('IMPOSSIBLE')
    exit()

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.add(b)
    if b == N:
        goal.add(a)
    
if len(start & goal) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

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

s = set()
g = set()

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


ans = len(s & g) > 0
print("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

Solution code:


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

s = set()
g = set()

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


ans = len(s & g) > 0
print("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
memo = [False] * n

possible = False
for _ in range(m):
    s, e = map(int, input().split())

    if s == 1:
        if memo[e]:
            possible = True
            break

        memo[e] = True

    elif e == n:
        if memo[s]:
            possible = True
            break

        memo[s] = True

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

Submission status: Accepted

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