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())
an = []
nb = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.append(b)
    elif b == N:
        nb.append(a)

print('IMPOSSIBLE' if len(set(an)&set(nb))==0 else 'POSSIBLE')

Submission status: Accepted

Solution code:
#真に大切なのは中間点となる要素
N, M = map(int, input().split())
an = set()
nb = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.add(b)
    elif b == N:
        nb.add(a)

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    d = {}
    for ab in AB:
        if ab[0] not in d:
            d[ab[0]] = [ab[1]]
        else:
            d[ab[0]].append(ab[1])
    if 1 not in d:
        print("IMPOSSIBLE")
        return
    for i in d[1]:
        if i not in d:
            continue
        if N in d[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")



if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

x=set(p1)
y=set(pn)
if x&y==set():
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Accepted

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

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
    for p in path[0]:
        if N-1 in path[p]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
    return 
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

n, m = map(int,input().split())
a = []

for i in range(m):
  x, y = map(int,input().split())
  if x == 1: #1の島から行ける島
    a.append(y)
  if y == n: #5の島へ行ける島
    a.append(x)

c = collections.Counter(a)

if c.most_common()[0][1] == 2:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
E = {i+1: set() for i in range(N)}
first = set()
for m in range(M):
    a, b = lr()
    if b == N:
        first.add(a)
    E[a].add(b)
if not first.isdisjoint(E[1]):
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m =map(int,input().split())
visited = False
q = [[] for _ in range(n)]
flag = False
for j in range(m):
    a,b = map(int,input().split())
    q[a].append(b)

while q[1]:
    c = q[1].pop()
    if n in q[c]:
        flag = True
print('POSSIBLE' if flag==True else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[set() for _ in range(N)]
    for i in range(M):
        a,b=map(int1,input().split())
        edge[a].add(b)
        edge[b].add(a)
    for i in range(N):
        if i in edge[0] and N-1 in edge[i]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a, b = [0] * m, [0] * m
root_i = [False] * n
root_n = [False] * n
for i in range(m):
    a[i], b[i] = map(int, input().split())

for i in range(m):
    if a[i] == 1:
        root_i[b[i]] = True
    elif b[i] == n:
        root_n[a[i]] = True

for i in range(n):
    if root_i[i] == True and root_n[i] == True:
        print("POSSIBLE")
        exit()
    
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
one_to=[0]*(n+1)
to_n=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        one_to[b]=1
    elif b==n:
        to_n[a]=1
flag=False
for i in range(2,n):
    if one_to[i]==1 and to_n[i]==1:
        flag=True
        break
print("POSSIBLE" if flag else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
one_to=set()
to_n=set()
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        one_to.add(b)
    elif b==n:
        to_n.add(a)
one_to=list(one_to)
flag=False
for i in range(len(one_to)):
    if one_to[i] in to_n:
        flag=True
        break
print("POSSIBLE" if flag else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int,input().split())
d = defaultdict(int)
for _ in range(M):
    a, b = map(int,input().split())
    if a == 1:
        d[b] += 1
    if b == N:
        d[a] += 1
if 2 in d.values():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if a==0: A[b]+=1
    elif b==n-1: A[a]+=1
ok = False
for i in range(1,n-1):
    if A[i]>=2:
        ok = True
        break
if ok: print("POSSIBLE")
else: print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
nim,mike = map(int,input().split())
a = set()
b = set()
for i in range(mike):
    a_,b_ = map(int,input().split())
    if a_ == 1:
        a.add(b_)
    if b_ == nim:
        b.add(a_)
print("POSSIBLE" if a&b else "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)

if sa&sb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def slove(n, ab_list):

    hoge = {}
    for i,j in ab_list:
        if int(i) not in hoge:
            hoge[int(i)] = []
        hoge[int(i)].append(int(j))

    ans = len([j for i in hoge[1] if i in hoge for j in hoge[i] if j == n])

    if ans >=1:
        return "POSSIBLE"
    else:
        return "IMPOSSIBLE" 

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    ab_list = [input().split() for i in range(m)]
    print(slove(n, ab_list))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
li=[]
for i in range(m):
    a,b=map(int,input().split())
    li.append([a,b])
li1=set([i[1] for i in li if i[0]==1])
li2=set([i[0] for i in li if i[1]==n])
li3=li1&li2
if len(li3)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = [0 for i in range(M)]
for i in range(M):
    s[i] = list(map(int, input().split()))
ex = [[0] * 2 for i in range(N)]
for i in range(M):
    if s[i][0] == 1:
        ex[(s[i][1] - 1)][0] = 1
    if s[i][1] == N:
        ex[(s[i][0] - 1)][1] = 1
if [1, 1] in ex:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [0] * n
r = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        r.append(b)
    if b == n:
        l[a - 1] = 1
ans = "IMPOSSIBLE"
for i in r:
    if l[i - 1] == 1:
        ans = "POSSIBLE"
print(ans)

Submission status: Accepted

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

for _ in range(M):
  a,b = map(int,input().split())
  if a == 1:
    if tmp[b-1] == 1:
      print('POSSIBLE')
      exit()
    else:
      tmp[b-1] = 1
  elif b == N:
    if tmp[a-1] == 1:
      print('POSSIBLE')
      exit()
    else:
      tmp[a-1] = 1
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
tmp = [False] * N
for _ in range(M):
  a,b = map(int, input().split())
  if a == 1:
    if tmp[b-1]:
      print('POSSIBLE')
      exit()
    else:
      tmp[b-1] = True
  elif b == N:
    if tmp[a-1]:
      print('POSSIBLE')
      exit()
    else:
      tmp[a-1] = True
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
check=[0]*n
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if check[bi-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[bi-1]+=1
    elif bi==n:
        if check[ai-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[ai-1]+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    S = set()
    E = set()
    for m in range(M):
        a, b = il()
        if a == 1:
            S.add(b)
        if b == N:
            E.add(a)

    print('POSSIBLE' if len(S & E) == 1 else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
c1x=set([x[1] for x in ab if x[0]==1])
cxn=set([x[0] for x in ab if x[1]==n])
print('POSSIBLE'if len(c1x & cxn)>0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] = True
    if b == n:
        d[a] = True
for i in range(n):
    if c[i] and d[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] = True 
    if b == n:
        d[a] = True
        
flag = False
for i in range(200000):
    if c[i] and d[i]:
        flag = True
        break
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
	a, b = map(int, input().split())
	if a == 1:
		c[b] = True
	if b == n:
		d[a] = True
for i in range(200000):
	if c[i] and d[i]:
		print ("POSSIBLE")
		exit()
print ("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = [False for i in range(200001)]
d = [False for i in range(200001)]
for i in range(m):
	a, b = map(int, input().split())
	if a == 1:
		c[b] = True
	if b == n:
		d[a] = True
for i in range(200001):
	if c[i] and d[i]:
		print ("POSSIBLE")
		exit()
print ("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(m):
    a, b = map(int, input().split())
    if a==1:
        root[0][b-1] = True
    if b==n:
        root[1][a-1] = True
for j in range(n):
    if root[0][j]:
        if root[1][j]:
            print('POSSIBLE')
            exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

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

C, D = set(), set()
for a, b in AB:
  if a == 1:
    C.add(b)
  elif b == n:
    D.add(a)

if len(C & D):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

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

ans = False
# cnt (0, 1, 2, ..., N - 1)
cnt = [0 for i in range(0, N)]
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cnt[b] += 1
        if cnt[b] == 2:
            ans = True
            break
    elif b == N:
        cnt[a] += 1
        if cnt[a] == 2:
            ans = True
            break

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(m)]
list_MAP = [0]*(n+1)

for l in list_AB:
    l.sort()
    if l[0] == 1:
        list_MAP[l[1]] += 1
    if l[1] == n:
        list_MAP[l[0]] += 1

ans = "IMPOSSIBLE"

for num in list_MAP:
    if num > 1:
        ans = "POSSIBLE"

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, m = [int(i) for i in input().split()]

connected_1 = {}

for i in range(m):
    a, b = [int(i) for i in input().split()]
    
    if a == 1:
        if connected_1.get(b) is None:
            connected_1[b] = 1
        elif connected_1[b] ==1:
            print("POSSIBLE")
            break
        
        
    if b == n:
        if connected_1.get(a) is None:
            connected_1[a] = 1
        elif connected_1[a] ==1:
            print("POSSIBLE")
            break
        
       
        
    if i==m-1:
        print("IMPOSSIBLE")

Submission status: Accepted

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

A = 0
B = 1
cnt = [0] * (n+1)
ab = []

for i in range(m):
    a,b = map(int, input().split())
    ab.append([a, b])
    if a == 1:
        cnt[b] += 1
    elif b == n:
        cnt[a] += 1

for i in range(n+1):
    if cnt[i] == 2:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

A = 0
B = 1
mid = [0] * (n+1)
goal = [0] * (n+1)
ab = []

for i in range(m):
    a,b = map(int, input().split())
    ab.append([a, b])
    if a == 1:
        mid[b] += 1
    elif b == n:
        goal[a] += 1

# print(mid)
# print(goal)

for i in range(n+1):
    if mid[i] == 1 and goal[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l =[ list(map(int,input().split())) for i in range(m)]
l1 = set([i[1] for i in l if i[0]==1])
l2 = set([i[0] for i in l if i[1]==n])
l3 = l1&l2
if len(l3)>=1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
src = set()
dst = set()
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        dst.add(b)
    if b == 1:
        dst.add(a)
    if a == n:
        src.add(b)
    if b == n:
        src.add(a)
print('POSSIBLE' if len(src & dst) > 0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
graph = [set() for _ in range(n + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].add(b); graph[b].add(a)

def main():
    ans = 'IMPOSSIBLE'
    for x in graph[1]:
        if n in graph[x]:
            ans = 'POSSIBLE'
            break
    print(ans)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s1=[]
sn=[]
ans='IMPOSSIBLE'
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    s1.append(b)
  elif b==n:
    sn.append(a)
s=sorted(s1+sn)
for i in range(len(s)-1):
  if s[i]==s[i+1]:
    ans='POSSIBLE'
    break
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s1=set()
sn=set()
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    s1.add(b)
  if b==N:
    sn.add(a)
print("POSSIBLE" if len(s1&sn)!=0 else "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:
n,m=map(int,input().split())
shima=dict()
for i in range(m):
    a,b=map(int,input().split())
    if a not in shima:
        shima[a]=[b]
    else:
        x=shima[a]
        x.append(b)
        shima[a]=x

flag=False
start=0

if 1 in shima:
    for next_shima in shima[1]:
        if next_shima in shima:
            if n in shima[next_shima]:
                flag=True 


#print(shima)

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

Submission status: Accepted

Solution code:
def main():
    n, m = input().split()
    g1 = []
    g2 = []
    for _ in range(int(m)):
        x, y = input().split()
        if x == '1':
            g1.append(y)
        elif y == n:
            g2.append(x)
    sx = set(g1)
    sy = set(g2)
    sxy = sx.intersection(sy)
    if len(sxy):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    g1 = []
    g2 = []
    for _ in range(m):
        x, y = map(int, input().split())
        if x == 1:
            g1.append(y)
        elif y == n:
            g2.append(x)
    sx = set(g1)
    sy = set(g2)
    sxy = sx.intersection(sy)
    if len(sxy):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = list(map(int, input().split()))
lsta = [0 for i in range(n+1)]
lstb = [0 for i in range(n+1)]

for i in range(m):
    a,b = list(map(int, input().split()))
    if a==1:
        lsta[b]=1
    if b==n:
        lstb[a]=1

for i in range(n+1):
    if lsta[i]==1 and lstb[i]==1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque

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

f_inf = float("inf")
dist = [f_inf for _ in range(n)]
dist[0] = 0
q = deque()
q.append(0)
while q:
    u = q.popleft()
    for nv in tree[u]:
        if dist[nv] == f_inf:
            dist[nv] = dist[u] + 1
            q.append(nv)
if dist[n - 1] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab_list = [0] * m
for i in range(m):
	ab_list[i] = list(map(int, input().split()))
a_list = []
b_list = []
for i in ab_list:
	if i[0] == 1:
		a_list.append(i[1])
	elif i[1] == n:
		b_list.append(i[0])
r = 'POSSIBLE' if set(a_list) & set(b_list) else 'IMPOSSIBLE'
print(r)

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
  n,m = readInts()
  A = set()
  B = set()
  for i in range(m):
    a,b = input().split()
    if a == '1':
      A.add(b)
    if b == str(n):
      B.add(a)
  print('POSSIBLE' if A & B else 'IMPOSSIBLE')
  # A & B 共通のものがあればよい
  # A = [3] B = [3]とかなら 1 - 3 , 3 - 6への経路がある！！
if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
a,b = [],[]
for x in l:
    if x[0] == 1:
        a.append(x[1])
    if x[1] == n:
        b.append(x[0])
print ('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
N,M = map(int,input().split())
T = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
D = [5]*(N+1)
Q = [(0,1)]
while Q:
    cost,v = heappop(Q)
    if cost>2 or cost>=D[v]:continue
    D[v] = cost
    for c in T[v]:
        heappush(Q, (cost+1, c))
print("POSSIBLE" if D[N]<=2 else "IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

import queue
voi = [100] * (n + 1)
tf = [False] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put(v)
    tf[v] = True
    voi[v] = 0
    while not q.empty():
        now = q.get()
        for nex in graph[now]:
            if tf[nex]:
                continue
            q.put(nex)
            voi[nex] = voi[now] + 1
            tf[nex] = True

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k,l=set(),set()
for i in range(m):
  s=list(map(int,input().split()))
  if 1 in s:
    k|={s[1]}
  if n in s:
    l|={s[0]}
print('POSSIBLE' if len(k&l)>0 else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
start = []
goal = []
for i in ab:
  if i[0] == 1:
    start.append(i[1])
  elif i[1] == n:
    goal.append(i[0])
p = start + goal
if len(p) == len(list(set(p))):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Accepted

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

a = []
b = []
for x in l:
    if x[0] == 1:
        a.append(x[1])
    if x[1] == n:
        b.append(x[0])

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

Submission status: Accepted

Solution code:
S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])


def calculate(n,m,arr):
    tmp = []
    tmp2 = {}

    for ar in arr:
        f = ar[0]
        t = ar[1]
        if f == 1:
           tmp.append(t)

        tmp2.__setitem__((f,t),True)

    if tmp2.get((1,N)) == True:
        print("POSSIBLE")
        return

    for tm in tmp:
        if tmp2.get((tm,N)) == True:
            print("POSSIBLE")
            return


    print("IMPOSSIBLE")



calculate(N,M,ARR)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def int_(num_str):
    return int(num_str) - 1


N, M = map(int, input().split())
graph = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int_, input().split())
    graph[a].add(b)
    graph[b].add(a)
for i in range(1, N-1):
    if (0 in graph[i]) and (N-1 in graph[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 i in range(m)]
a = []
b = []
for i in ab:
    if i[0] == 1:
        b.append(i[1])
    elif i[1] == n:
        a.append(i[0])
if len(set(a) & set(b)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

flag = False
for kk in t.keys():
    if kk in fr:
        flag = True
        break

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[0]*M;p=-1

for i in range(M):
    a,b=map(int,input().split())
    A[i]=[a,b]
A.sort(reverse=True, key=lambda x: x[1])
#print(A)
#print("Yes" if A[0][1]==N else "No")

if A[0][1]!=N:
    print("IMPOSSIBLE")
else:
    d = [False] * (N + 5)
    for i in range(M):
        if A[i][1] == N:
            d[A[i][0]] = True
        if A[i][0] == 1 and d[A[i][1]]:
            p = 2
            #print(1,A[i][0],A[i][1],A[0][0],p)
    if p == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Submission status: Accepted

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

a_list = []
tmp_start = []
tmp_goal = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp_start.append(b)
    
    if b == n:
        tmp_goal.append(a)
    

    # 島1から意外の運航便のリスト
    #else:
    #    a_list.append([a, b])

agree = set(tmp_start) & set(tmp_goal)

if len(agree) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

#for j in tmp_start:
#    if j in tmp_goal:
#        print('POSSIBLE')
#        break

#else:
#    print('IMPOSSIBLE')

Submission status: Accepted

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

middles1 = []
middles2 = []
ans = "IMPOSSIBLE"

for i in l:
    if i[0] == 1 and i[1] == N:
        ans = "POSSIBLE"
    elif i[0] == 1:
        middles1.append(i[1])
    elif i[1] == N:
        middles2.append(i[0])

if len(set(middles1) & set(middles2)) > 0:
    ans = "POSSIBLE"

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

path = [float('inf')] * N
q = deque()
q.append((0, 0))
path[0] = 0
while q:
    p, step = q.popleft()
    for np in edge[p]:
        nstep = step + 1
        if path[np] > nstep and nstep <= 2:
            q.append((np, nstep))
            path[np] = nstep

ans = 'POSSIBLE' if path[N - 1] == 2 else 'IMPOSSIBLE'
print(ans)

Submission status: Accepted

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

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

transit = []
transit_ = []

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

if set(transit)&set(transit_):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

transit = []
transit_ = []

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

if set(transit)&set(transit_):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque
# g : グラフ
# 例 [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
# i : 始点
def bfs(g, i):
    
    #各頂点への距離
    dis = [float('Inf')] * N 
    
    #訪れたかどうか
    d = [False] * N
    #初期設定
    que = deque()
    que.append(i)
    d[i] = True
    dis[i] = 0
    
    while que:
        p = que.popleft()
        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[k] = dis[p] + 1

    return dis
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
g = [[] for _ in range(N)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
dis = bfs(g, 0)

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

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
a1=set()
an=set()
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.add(bi)
    elif bi==n:
        an.add(ai)

if len(a1&an)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

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

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")