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:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,m = i_map()
    s = set()
    g = set()

    for _ in range(m):
        a,b = i_map()
        if a == 1:
            s.add(b)
        elif b == 1:
            s.add(a)
        elif a == n:
            g.add(b)
        elif b == n:
            g.add(a)

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
L = [list(map(int, input().split())) for i in range(M)]
s = []
g = []
for i in range(M):
    if 1 == L[i][0]:
        s.append(L[i][1])
    if 1 == L[i][1]:
        s.append(L[i][0])
        
for i in range(M):
    if N == L[i][0]:
        g.append(L[i][1])
    if N == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,M = mint()
ship = [set() for _ in range(N+1)]
for _ in range(M):
    a,b = mint()
    ship[a].add(b)
    ship[b].add(a)
ans = False
for a in ship[1]:
    if N in ship[a]:
        ans = True
        break
judge(ans,['POSSIBLE','IMPOSSIBLE'])

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode
import sys
sys.setrecursionlimit(10 ** 6)

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n,m = MI()
ab = LI(m)

ls_s = []
ls_e = []
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    if a==1:
        ls_s.append(b)
    elif b==n:
        ls_e.append(a)

ls = set(ls_s) & set(ls_e)
if len(ls)!=0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
def ipnput():
    return sys.stdin.readline()[:-1]
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edg1=[0]*(n+1)
edgn=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        edg1[b]=1
    if b==n:
        edgn[a]=1

f=1
for i in range(2,n+1):
    if edg1[i]==1 and edgn[i]==1:
        f=0
print("POSSIBLE" if f==0 else "IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
l = [[] for i in range(n)]
ab.sort()
for i in range(m):
    x = ab[i]
    l[x[0]-1].append(x[1]-1)
    l[x[1]-1].append(x[0]-1)
for i in l[0]:
    if n-1 in l[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M = MI()
d1 = {}  # d1[i] = 島1と島iの間に定期便が存在するか
d2 = {}  # d1[i] = 島Nと島iの間に定期便が存在するか
for i in range(1,N+1):
    d1[i] = 0
    d2[i] = 0
for _ in range(M):
    a,b = MI()
    if a == 1:
        d1[b] = 1
    if b == N:
        d2[a] = 1
for i in d1.keys():
    if d1[i] == d2[i] == 1:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict

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

g = defaultdict(list)

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

visited = [False]*n

q = [0]
visTime = 0
Found = False
while q and visTime < 2:
    
    nL = []
    for vert in q:
        visited[vert] = True
        for v in g[vert]:
            if v == n-1:
                Found = True
                break
            if not visited[v]:
                nL.append(v)
    if Found:
        break
    q = nL
    visTime += 1
    
print('POSSIBLE' if Found else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque


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

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

def main():
    dist = [-1] * N
    dist[0] = 0
    que = deque([0])
    
    while que:
        v = que.popleft()
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                que.append(nv)
                
    print('POSSIBLE' if dist[N - 1] == 2 else 'IMPOSSIBLE')
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#55 C - Cat Snuke and a Voyage
from collections import deque
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
        
if dist[N-1] == 2:
    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 i in range(m):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
dis = [200000 for i in range(n)]
dis[0] = 0
Q = deque([0])
while Q:
    now = deque.popleft(Q)
    for i in E[now]:
        if dis[i] == 200000:
            dis[i] = dis[now]+1
            deque.append(Q, i)
print("POSSIBLE" if dis[-1] == 2 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
voyage = [set() for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  voyage[a].add(b)
  voyage[b].add(a)
ans = 0
for v in voyage[1]:
  if v in voyage[n]:
    ans = 1
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
import collections
[n,m] = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(m):
  [a,b] = [int(j)-1 for j in input().split()]
  if a == 0:
    dic[b] += 1
  elif b == n-1:
    dic[a] += 1
if max(dic.values()) >= 2:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#
# abc068 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 2
1 2
2 3"""
        output = """POSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 3
1 2
2 3
3 4"""
        output = """IMPOSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000 1
1 99999"""
        output = """IMPOSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5 5
1 3
4 5
2 3
2 4
1 4"""
        output = """POSSIBLE"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    S = [0] * N
    E = [0] * N
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            S[b-1] = 1
        if b == N:
            E[a-1] = 1

    ans = "IMPOSSIBLE"
    for i in range(N):
        if S[i] == E[i] == 1:
            ans = "POSSIBLE"
            break
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

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())
'''
check = 0


for i in range(m):
    if a[i] == 1:
        check = b[i]
        for j in range(m):
            if a[j] == check and b[j] == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

'''
start = []
leave = []
for i in range(m):
    if a[i] == 1:
        start.append(b[i])
    elif b[i] == n:
        leave.append(a[i])

if set(start) & set(leave):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

hyou=[]

for i in range(m):
    hyou.append([int(i) for i in input().split()])


next_island=set()
pre_island=set()
for go in hyou:
    one,two=go
    newone=min(one,two)
    newtwo=max(one,two)

    if newone==1:
        next_island.add(newtwo)
    if newtwo==n:
        pre_island.add(newone)

ans=next_island&pre_island

if len(ans)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
nekotyann=[0]*N
wanntyann=[0]*N
ans="IMPOSSIBLE"
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        nekotyann[b-1]+=1
    if b==N:
        wanntyann[a-1]+=1
for k in range(N):
    if nekotyann[k]!=0 and wanntyann[k]!=0:
        ans="POSSIBLE"
        break
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
for i in edge[0]:
    if n-1 in edge[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
#隣接リスト
g = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  g[a-1].append(b)
  g[b-1].append(a)
ls = g[0]
flag = 0
for i in range(len(g[0])):
  ls2 = g[ls[i]-1]
  for j in range(len(ls2)):
    if ls2[j] == N:
      flag += 1
      print("POSSIBLE")
      break
if flag == 0:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
#隣接リスト
g = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  g[a-1].append(b)
  g[b-1].append(a)
ls = g[0]
flag = 0
for i in range(len(g[0])):
  ls2 = g[ls[i]-1]
  for j in range(len(ls2)):
    if ls2[j] == N:
      flag += 1
      print("POSSIBLE")
      break
if flag == 0:
  print("IMPOSSIBLE")

Submission status: Accepted

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

cnt = 0
for i in x[0]:
    if n in x[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ab_s = [list(map(int,input().split())) for _ in range(M)]
ONES = set()
NS = set()
for ab in ab_s:
    a = ab[0]
    b = ab[1]
    if a==1 or b==1:
        if a in NS or b in NS:
            print('POSSIBLE')
            break
        ONES.add(a)
        ONES.add(b)
    if a==N or b==N:
        if a in ONES or b in ONES:
            print('POSSIBLE')
            break
        NS.add(a)
        NS.add(b)
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
from collections import defaultdict
G=defaultdict(lambda: [])
for _ in range(M):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
for nx in G[1]:
    if N in G[nx]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

dic = {}
for i in range(m):
    a, b = map(int, input().split())
    dic[(a, b)] = True
    dic[(b, a)] = True
ans = 'IMPOSSIBLE'
for i in range(2, n):
    if dic.get((1, i), False):
        if dic.get((i, n), False):
            ans = 'POSSIBLE'
            break
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)

for i in edge[0]:
    if n - 1 in edge[i]:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import collections

n,m=map(int,input().split())
a,b,c=[],[],[]
for i in range(m):
    A=list(map(int,input().split()))
    a.append(A)
for i in range(m):
    if a[i][1]==n:
        b.append(a[i][0])
    elif a[i][0]==1:
        c.append(a[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())
ans = ('IMPOSSIBLE')
f1tob = []
fbtoN = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        f1tob.append(b)
    elif b == N:
        fbtoN.append(a)
f1toba = set(f1tob)
fbtoNa = set(fbtoN)
if bool(fbtoNa & f1toba):
    ans = 'POSSIBLE'
print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    ans = False

    for i in route[n]:
        if 1 in route[i]:
            ans = True
    print("POSSIBLE" if ans else "IMPOSSIBLE")
        

main()

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:
        g.add(b)
    if b == n:
        s.add(a)
x = s & g
if x:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

G = [[] for j in range(n + 1)]

for a, b in edges:
    G[a].append(b)
    G[b].append(a)

for b in G[1]:
    if n in G[b]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

dic1 = {}
for i in range(M):
    a,b = map(int,input().split())
    a,b = min(a,b),max(a,b)
    if b == N:
        dic[a]=0
    if a==1:
        dic1[b]=0
ans = False
for tmp in dic1:
    if tmp in dic:
        ans = True
        break
print("POSSIBLE" if ans else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
start = [0]*200001
goal = [0]*200001

for i in range(m):
  a,b = map(int,input().split())
  if a == 1:
    if goal[b] == 1:
      print("POSSIBLE")
      exit()
    start[b] = 1
    a
  elif b == n:
    if start[a] == 1:
      print("POSSIBLE")
      exit()
    goal[a] = 1
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
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)
if A&B:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
def main():
  N, M = map(int,input().split())
  fromOne = set()
  toM = set()
  for i in range(M):
    a, b = map(int,input().split())
    if a == 1:
      fromOne.add(b)
    elif b == N:
      toM.add(a)
  return 'POSSIBLE' if fromOne & toM else 'IMPOSSIBLE'
print(main())

Submission status: Accepted

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

t = [0]*(n+1)

for _ in range(m):
    a, b = inintm()
    if a == 1:
        if t[b] == 1:
            print("POSSIBLE")
            exit()
        t[b] = 1
    elif b == n:
        if t[a] == 1:
            print("POSSIBLE")
            exit()
        t[a] = 1

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

graph = defaultdict(list)

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

for hop in graph[1]:
    for goal in graph[hop]:
        if goal == n:
            print("POSSIBLE")
            quit()
        else:
            continue

print("IMPOSSIBLE")

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    from_one = set([])
    to_n = set([])
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from_one.add(b)
        elif b == N:
            to_n.add(a)
    if len(from_one & to_n) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(("IMPOSSIBLE","POSSIBLE")[len(set(N_List) & set(O_List)) > 0])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

for v in connections[1]:
    if N in connections[v]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque

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

e = [[] for i in range(n)]
for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    e[f].append(t)
    e[t].append(f)

INF = 10**9
dist = [INF] * n
dist[0] = 0
d = deque()
d.append([0, 0])

while d:
    f, c = d.pop()
    if c >= 2:
        break
    for t in e[f]:
        if c + 1 < dist[t]:
            dist[t] = c + 1
            d.appendleft([t, c+1])
print('POSSIBLE') if dist[n-1] <= 2 else print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
arr_ = [tuple(map(int, input().split())) for _ in range(m)]
one = set([b for a, b in arr_ if a == 1])
last = set([a for a, b in arr_ if b == n])
print("POSSIBLE" if len(one & last) >= 1 else "IMPOSSIBLE")

Submission status: Accepted

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

one = set([b for a, b in arr_ if a == 1])
last = set([a for a, b in arr_ if b == n])
connect = one & last
if len(connect) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

one = set([b for a, b in arr if a == 1])
last = set([a for a, b in arr if b == n])
connect = one & last
if len(connect) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ini_1 = []
end_n = []
for i in range(m):
    if ab[i][0] == 1:
        ini_1.append(ab[i][1])
    elif ab[i][1] == n:
        end_n.append(ab[i][0])
if set(ini_1) & set(end_n):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)] 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections as c
n,m=map(int,input().split())
print(['POSSIBLE','IMPOSSIBLE'][not [1 for c in c.Counter([[a,b][a==1] for a,b in [[i,j] for i,j in [list(map(int,input().split())) for _ in range(m)] if i==1 or j==n]]).values() if c>1]])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque

# input
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())

if m == 1:
    print('IMPOSSIBLE')
    exit()

to = [[] for _ in range(n+1)]
for i in range(m):
    to[a[i]].append(b[i])
    to[b[i]].append(a[i])
#print('to =', to)

# BFS
inf = 200200
dist = [inf for _ in range(n+1)]
q = deque()
q.append(1)
dist[1] = 0 

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] == inf:
            dist[u] = dist[v]+1
            q.append(u)

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

Submission status: Accepted

Solution code:
N,M=list(map(int, input().split()))
S=set()
D=[]
for i in range(M):
    l=list(map(int, input().split()))
    if l[0]==1:
        S.add(l[1])
    else:
        D.append(l)
# print(S)
# print(D)
D.sort()
L=len(D)
for i in range(L):
    if D[i][1]==N and D[i][0] in S:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
island = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    island[a].append(b)

for i in island[1]:
    if N in island[i]:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m, *AB = map(int, open(0).read().split())

C, D = set(), set()
for a, b in zip(AB[::2], AB[1::2]):
  if a == 1:
    C.add(b)
  if 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())
init_island = set()
last_island = set()
for _ in range(m):
    a,b = map(int,input().split())
    a,b = min(a,b), max(a,b)
    if a == 1:
        init_island.add(b)
    elif b == n:
        last_island.add(a)
    else:
        continue
common = init_island.intersection(last_island)
if len(common) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

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

N = n-1
for i in g[0]:
    if N in g[i]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')