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())
a = []
b = []
ans = ""
for i in range(m):
    tmp1,tmp2 = map(int,input().split())
    a.append(tmp1)
    b.append(tmp2)

xton = set()
#nへ向かう便が出てる島を確認する
for i in range(m):
    if b[i] == n:
        xton.add(a[i])
#nへ向かう便が出ている島へ1から向かう便があるか確認する
for i in range(m):
    if a[i] == 1 and b[i] in xton:
        ans = "POSSIBLE"
        break
    else:
        ans = "IMPOSSIBLE"
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
seta = set(start)
setg = set(goal)
for i in seta:
    if i in setg:
        ans = 'POSSIBLE'
        break
print(ans)

Submission status: Accepted

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

x = []
y = []
for a, b in ab:
    if a == 1:
        x.append(b)
    if b == n:
        y.append(a)

if len(set(x) & set(y)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N, M = [int(x) for x in input().split()]
I = []
for _ in range(M):
    I.append([int(x) for x in input().split()])
s_1 = set()
s_N = set()
for i in I:
    if i[0] == 1 and i[1] == N:
        print("POSSIBLE")
        sys.exit()
    if i[0] == 1:
        if i[1] in s_N:
            print("POSSIBLE")
            sys.exit()
        s_1.add(i[1])
    if i[1] == N:
        if i[0] in s_1:
            print("POSSIBLE")
            sys.exit()
        s_N.add(i[0])
for j in s_1:
    if j in s_N:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[list(map(int,input().split())) for i in range(m)]
lis=[]
for i in range(m):
  if g[i][0]==1:
    lis.append(g[i][1])
  if g[i][1]==n:
    lis.append(g[i][0])
lis.sort()
if len(lis)<2:
  print('IMPOSSIBLE')
else:
  for i in range(len(lis)-1):
    if lis[i]==lis[i+1]:
      print('POSSIBLE')
      exit()
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
g_1 = set()
g_n = set()
for a, b in zip(*[iter(ab)] * 2):
    if a == 1 or b == 1:
        g_1.add(b)
    elif a == n or b == n:
        g_n.add(a)

def main():
    return 'POSSIBLE' if g_1 & g_n else 'IMPOSSIBLE'

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

Submission status: Accepted

Solution code:
import sys

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

def main():
    return 'POSSIBLE' if g[1] & g[n] else 'IMPOSSIBLE'

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
tr=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  if a!=1 and b!=n:
    continue
  if a==1:
    if tr[b]==[n]:
      print("POSSIBLE")
      exit()
    else:
      tr[b].append(a)
  if b==n:
    if tr[a]==[1]:
      print("POSSIBLE")
      exit()
    else:
      tr[a].append(b)
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
tr=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  if a!=1 and b!=n:
    continue
  tr[a].append(b)
  tr[b].append(a)
for i in range(2,n):
  if len(tr[i])==2:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal2 = []
goal1 = []
for i in range(M):
    if A[i][1] == N:
        goal2.append(A[i][0])
    elif A[i][0] == 1:
        goal1.append(A[i][1])
    else:
        pass

if len(set(goal1)&set(goal2)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

transfer_1 = set()
transfer_2 = set()

for i in range(m):
  a, b = list(map(int, input().split()))
  if(a == 1):
    transfer_1.add(b)
  if(b == n):
    transfer_2.add(a)
s_intersection = transfer_1 & transfer_2
print("POSSIBLE" if len(s_intersection) else "IMPOSSIBLE")

Submission status: Accepted

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

from_1 = []
to_n = []

for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
      from_1.append(b)
    if a == n:
      to_n.append(b)
    if b == 1:
      from_1.append(a)
    if b == n:
        to_n.append(a)

if len(set(from_1) & set(to_n)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

    node_1 = set()  # 島 1 から定期便で行き来できる島
    node_n = set()  # 島 N から定期便で行き来できる島
    for a, b in Ships:
        if a == 1:
            node_1.add(b)
        if b == N:
            node_n.add(a)
    return 'POSSIBLE' if [1 for i in node_1 if i in node_n] else 'IMPOSSIBLE'
print(c_cat_snuke_and_a_voyage())

Submission status: Accepted

Solution code:
# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回c
# なんかしらんけどdfsが2TLEになるので諦めた それぞれの島について1とNがあれば良い

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)

for g in graph[1 : n - 1]:
    c = 0
    for v in g:
        if c >= 2:
            break
        if v == 0 or v == n - 1:
            c += 1
    if c == 2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


N,M = two_int()

from collections import defaultdict
start_dicts =defaultdict(list)
end_dicts = defaultdict(list)
for i in range(M):
    a,b = two_int()

    if a in start_dicts:
        start_dicts[a].append(b)
    else:
        start_dicts[a] =[b]

        
    if b in end_dicts:
        end_dicts[b].append(a)
    else:
        end_dicts[b] =[a]


if len(set(start_dicts[1]) & set(end_dicts[N]))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

aedge = set()
bedge = set()

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

print("POSSIBLE" if len(aedge & bedge) else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
adj = [[] for i in range(n + 1)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
dist = [-1 for i in range(n + 1)]
dist[1] = 0
Q = deque()
Q.append(1)
while len(Q) > 0:
	u = Q.popleft()
	for v in adj[u]:
		if dist[v] != -1:
			continue
		dist[v] = dist[u] + 1
		Q.append(v)
if dist[n] == 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[0])

t = {i:[] for i in range(1,N+1)}
for a, b in ab:
    if a == 1:
        t[a].append(b)
    elif b == N:
        t[a].append(N)

for i in t[1]:
    if len(t[i]) == 1:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
transit = [False] * n
for i in range(m):
    index = float('inf')
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a == 0:
        index = b
    elif b == n - 1:
        index = a
    if index != float('inf'):
        if transit[index]:
            print('POSSIBLE')
            exit()
        else:
            transit[index] = True
print('IMPOSSIBLE')

Submission status: Accepted

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

pre = [0 for i in range(n+1)]
post = [0 for i in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        pre[b] = 1
    if b == n:
        post[a] = 1

for pr, po in zip(pre, post):
    if pr == 1 and po == 1:
        print("POSSIBLE")
        import sys
        sys.exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys,heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10**9+7
ans = 0 ;count = 0 ;pro = 1


def disktra(g,s):
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v,c in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

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

dist = disktra(g,0)
if dist[n-1]<=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

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

One_to = []
for i in range(m):
    if A_B[i][0] == 1:
        One_to.append(A_B[i][1])
    elif A_B[i][1] == 1:
        One_to.append(A_B[i][0])

N_to = []
for i in range(m):
    if A_B[i][0] == n:
        N_to.append(A_B[i][1])
    elif A_B[i][1] == n:
        N_to.append(A_B[i][0])

One_to_set = set(One_to)
N_to_set = set(N_to)
inter = One_to_set & N_to_set
if len(inter) >= 1:
    ans = 'POSSIBLE'
else:
    ans = 'IMPOSSIBLE'

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
if M == 1:
  print('IMPOSSIBLE')
else:
  L = [0 for i in range(N-1)]
  L.insert(0, [])
  for i in range(M):
    v = list(map(int, input().split()))
    if v[0] == 1:
      L[0].append(v[1])
    else:
      if v[1] >= L[v[0]-1]:
        L[v[0]-1] = v[1]
  c = 0
  for i in range(len(L[0])):
    if L[L[0][i]-1] == N:
      c += 1
      break
  if c == 0:
    print('IMPOSSIBLE')
  else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

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

A.sort(reverse=True)

B = [0] * N
B[0] = 1

for a in A:
	f = a[0]-1
	t = a[1]-1
	if f == 0:
		B[t] = 1

for a in A:
	f = a[0]-1
	t = a[1]-1
	if B[f] == 1:
		B[t] = 2

#print(B)
print("POSSIBLE" if B[-1] else "IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

N, M = list(map(int, input().split()))
T1 = [False]*(N+1)
TN = [False]*(N+1)

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

for t1, tn in zip(T1,TN):
    if t1 and tn:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    d = collections.defaultdict(list)
    for _ in range(m):
        a, b = list(map(int, readline().split()))
        if a == 1 or a == n:
            if a not in d[b]:
                d[b] += [a]
        elif b == 1 or b == n:
            if b not in d[a]:
                d[a] += [b]
    for k, v in d.items():
        if k != 1 and k != n:
            if len(v) == 2:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE")


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
d=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  d[a].append(b)
for s in d[1]:
  for f in d[s]:
    if f == n:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

def main():
    buf = input()
    buflist = buf.split()
    n = int(buflist[0])
    m = int(buflist[1])
    ab = []
    for i in range(m):
        buf = input()
        buflist = buf.split()
        ab.append(tuple(map(int, buflist)))

    ab.sort()
    dp = []
    for i in range(n+1):
        dp.append([False, False, False])
    dp[1][0] = True
    for i in range(m):
        if dp[ab[i][0]][0]:
            dp[ab[i][1]][1] = True
        if dp[ab[i][0]][1]:
            dp[ab[i][1]][2] = True
    if dp[n][2]:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
keiro=[]
relay_point=set()
for i in range(m):
    a,b=[int(i) for i in input().split()]
    if(a==1):
        relay_point.add(b)
    else:
        keiro.append([a,b])

for i in keiro:
    if(i[0] in relay_point):
        if(i[1]==n):
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]
s=[]
a = sorted(a,key = lambda x:-x[1])

#print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] < n:
        break
    else:
        c.append(a[i][0])
c=set(c)
a = sorted(a,key = lambda x:x[0])
for i in range(m):
    if a[i][0] > 1:
        break
    else:
        s.append(a[i][1])

    #if a[i][1] in c:
s=set(s)

for i in s:
    if i in c:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n,m=MI()
    start=set()
    goal=set()
    for _ in range(m):
        a,b=MI()
        if a>b:a,b=b,a
        if a==1:start.add(b)
        if b==n:goal.add(a)
    if start&goal:print("POSSIBLE")
    else:print("IMPOSSIBLE")
main()

Submission status: Accepted

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

se1 = set()
se2 = set()

for a,b in AB:
    if a>b:
        a,b = b,a
    if a==1:
        se1.add(b)
    if b==N:
        se2.add(a)

se = se1&se2
answer = 'POSSIBLE' if se else 'IMPOSSIBLE'
print(answer)

Submission status: Accepted

Solution code:
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)

for node0 in graph[0]:
    for node1 in graph[node0]:
        if node1 == N - 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

rel = [[] for _ in [0]*(n+1)]

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

for r in rel[1]:
  if n in rel[r]:
    print("POSSIBLE")
    exit()
        
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(2)]
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    if a == 0:
        graph[a][b] = 1
    if b == n - 1:
        graph[1][a] = 1
flg = False
for i in range(n):
    if graph[0][i] & graph[1][i]:
        flg = True
if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

stack=[]
stack.append([0,2,-1])
while stack:
  node=stack.pop()
  v=node[0]
  ship=node[1]
  parent=node[2]
  if v==N-1 and ship==0:
    print("POSSIBLE")
    break
  if ship<=0:
    continue
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,ship-1,v])
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
graph = [[]for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,N-1):
    if 0 in graph[i] and N-1 in graph[i]:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict
graph = defaultdict(list)
for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    graph[a].append(b)
    graph[b].append(a)

dist = [float('inf')] * n
dist[0] = 0

stack = []
for target in graph[0]:
    dist[target] = 1
    stack.append(target)

for s in stack:
    for target in graph[s]:
        dist[target] = min(dist[target], 2)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def search(L,e):
    def bsearch(L,e,l,h):
        if h==l:
            return L[l]==e
        m=(h+l)//2
        if L[m]==e:
            return True
        elif L[m]>e:
            if l==m:
                return False
            else:
                return bsearch(L,e,l,m-1)
        else:
            return bsearch(L,e,m+1,h)
    if len(L)==0:
        return False
    else:
        return bsearch(L,e,0,len(L)-1)
n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
a.sort(key=lambda x:x[1])
b=[]
for i in range(m):
    if a[i][0]==1:
        b.append(a[i][1])
#print(a)
for i in range(m):
    if a[i][1]==n and search(b,a[i][0]):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = [0]*n

for i in li:
    if i[0] == 1:
        lin[i[1]-1] += 1
    if i[1] == n:
        lin[i[0]-1] += 1

for i in lin:
    if i == 2:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int , input().split())
start = []
goal = []
for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        start.append(b)
    elif b == n:
        goal.append(a)
if len(set(start) & set(goal)) >= 1:
    print("POSSIBLE")
else:
    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:
n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(m)]

li = sorted(li,key = lambda x:x[0])
start = []
for i in range(m):
  if li[i][0] != 1:
    break
  else:
    start.append(li[i][1])
li = sorted(li,key = lambda x:-x[1])
goal = []
for i in range(m):
  if li[i][1] != n:
    break
  else:
    goal.append(li[i][0])
isec = set(start+goal)
if len(isec) == len(start)+len(goal):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")
#print(start)
#print(goal)

Submission status: Accepted

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

N, M = map(int, input().split())
s = []
g = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 and b == N:
        print("POSSIBLE")
        sys.exit()
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)

if len(set(s) & set(g)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = []
b = []
for _ in range(M):
    X, Y = map(int, input().split())
    if X == 1:
        a.append(Y)
    if Y == 1:
        a.append(X)
    if X == N:
        b.append(Y)
    if Y == N:
        b.append(X)
if len(set(a) & set(b)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    AB = list(zip(m, m))

    p1 = []
    p2 = []
    for a, b in AB:
        if a == 1:
            p1.append(b)
        if b == N:
            p2.append(a)

    if len(list(set(p1) & set(p2))) >= 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
one_to_other = set([b for a, b in ab if a == 1])
other_to_n = set([a for a, b in ab if b == N])

way = one_to_other & other_to_n
if len(way) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

E.sort()
L = []
idx = N
for i in range(M):
    if E[i][0] == 1:
        L.append(E[i][1])
    else:
        idx = i
        break
        
L.sort()
ans = "IMPOSSIBLE"
for i in L:
    while idx < M:
        if E[idx][0] == i:
            if E[idx][1] == N:
                ans = "POSSIBLE"
                idx = M
            else:
                idx += 1
        elif E[idx][0] < i:
            idx += 1
        else:
            break
            
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

one_list = set()
n_list = set()

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        one_list.add(b)
    if b == 1:
        one_list.add(a)
    if a == n:
        n_list.add(b)
    if b == n:
        n_list.add(a)

print('IMPOSSIBLE' if (one_list & n_list) == set() else 'POSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def bfs(n,e,fordfs):
    #点の数、スタートの点、有向グラフ
    W = [-1]*n
    #各点の状態量、最短距離とか,見たかどうかとか
    W[e] = 0
    que = deque()
    que.append(e)
    len = [float("inf")]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowlen==2:
                #ループが嫌な時
                return len
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len


def examC():
    N, M = LI()
    v = [[] for _ in range(N)]
    for i in range(M):
        a, b = LI()
        v[a-1].append(b-1)
        v[b-1].append(a-1)
    judge = bfs(N,0,v)
    if judge[-1]>2:
        ans = "IMPOSSIBLE"
    else:
        ans = "POSSIBLE"
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

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

Submission status: Accepted

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

first = []
second = []
for i in range(m):
    a = list(map(int, input().split()))
    if a[0] == 1:
        first.append(a[1])
    if a[1] == n:
        second.append(a[0])


if len(set(first) & set(second)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[],[]]
for i in range(m):
  a,b = sorted(map(int,input().split()))
  if a == 1:
    g[0].append(str(b))
  elif b == n:
    g[1].append(str(a))
g0 = set(g[0])
g1 = set(g[1])
if g0 & g1:
  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)]

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])
first_to = set(first_to)
to_dest = set(to_dest)

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import deque

def bfs(si, ei):
  q = deque()
  q.append([si,0])
  done = set([si])
  while len(q) > 0:
    prvi, prvcnt = q.popleft()
    for i in g[prvi]:
      if i in done:
        continue
        
      else:
        if prvcnt + 1 > 2:
          continue
          
        if i == ei: return 'POSSIBLE'
        else:
          q.append([i, prvcnt+1])
          done.add(i)
  return 'IMPOSSIBLE'

N,M = map(int,input().split())
g = {i:[] for i 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)

print(bfs(0,N-1))

Submission status: Accepted

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

n,m=map(int,input().split())
boola=[False]*(n+1)
boolb=[False]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  if b==n: boola[a]=True
  if a==1: boolb[b]=True

for i in range(2,n):
  if boola[i] and boolb[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# C - Cat Snuke and a Voyage

n,m = map(int,input().split())
a = [0]*m
b = [0]*m
l = [0]*200000
s = "IMPOSSIBLE"

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


for i in range(m):
    if (a[i] == 1):
        if (l[b[i]] == 1):
            s = "POSSIBLE"
            break
        else : l[b[i]] = 1
    if (b[i] == n):
        if (l[a[i]] == 1):
            s = "POSSIBLE"
            break
        else : l[a[i]] = 1

print(s)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [ list(map(int, input().split())) for _ in range(m) ]
A = { i[1] for i in ab if i[0]==1 }
B = { i[0] for i in ab if i[1]==n }
if A&B != set():
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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