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())
ab=[]
for _ in range(M):
    ab.append(tuple(map(int, input().split())))
#print(ab)

from_1=set([el[1] for el in ab if el[0]==1])
from_N=set([el[0] for el in ab if el[1]==N])
#print(from_1, from_N)
if from_1 & from_N:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, M = map(int, input().split())
    # AB = [list(map(int, input().split())) for _ in range(M)]
    from_1 = [False] * N
    to_N = [False] * N
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from_1[b - 1] = True
        elif b == N:
            to_N[a - 1] = True
    for i in range(1, N):
        if from_1[i] and to_N[i]:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

# input = sys.stdin.readline

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E = map(int, input().split())
    r = 0
    g = [[] for i in range(V)]

    for i in range(E):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        d = 1
        g[s].append((d, t))
        g[t].append((d, s))  # g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 10

    if dijkstra(V, g, r)[-1]==2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


resolve()

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")

Submission status: Accepted

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

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())
c=[0]*max(n,m)
for i in range(m):
  if a[i]==1:
    c[b[i]-1] |= 1
  if b[i]==n:
    c[a[i]-1] |= 2
print("POSSIBLE" if max(c)==3 else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main ():
    n,m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    g = [[] for _ in range(n+1)]
    for a,b in ab:
        g[a].append(b)
        g[b].append(a)
    if set(g[1]) & set(g[n]) != set([]):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ABC068C():
    N, M = map(int, input().split())
    flag = [[False, False] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            flag[b][0] = True
        elif b == N:
            flag[a][1] = True

    for i in range(N):
        if flag[i][0] and flag[i][1]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
    return

ABC068C()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
from collections import Counter
cc=Counter()
for _ in range(m):
    a,b=map(lambda x:int(x)-1, input().split())
    cc[(a,b)]=1
    cc[(b,a)]=1
for i in range(1,n-1):
    if cc[(0,i)] and cc[(i,n-1)]:
        print('POSSIBLE')
        import sys
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(m):
    j,k=map(int,input().split())
    A[j-1].append(k-1)
    A[k-1].append(j-1)
for i in range(len(A[0])):
    if n-1 in A[A[0][i]]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l1=[]
ln=[]

for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        l1.append(bi)
    if bi==n:
        ln.append(ai)
    

if len(set(l1) & set(ln))==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

ship1 = [False]*n
shipn = [False]*n
ans = "IMPOSSIBLE"
for i in range(m):
  a, b = map(int, input().split())
  if a == 0 and b == n-1:
    ans = "POSSIBLE"
  elif a == 1:
    ship1[b-1] = True
  elif b == n:
    shipn[a-1] = True
  else:
    pass

for i in range(n):
  if ship1[i] and shipn[i]:
    ans = "POSSIBLE"
print(ans)

Submission status: Accepted

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

ab1 = []
ab2 = []

for i in ab:
    if i[0] == 1:
        ab1.append(i[1])
    elif i[1] == n:
        ab2.append(i[0])

jud = ab1 + ab2
if len(jud) == len(set(jud)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
l=[0]*n
for i in range(m):
  a,b=f()
  if a==1: l[b]+=1
  if b==n: l[a]+=1
print('IM'*(max(l)<2)+'POSSIBLE')

Submission status: Accepted

Solution code:
import numpy as np

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

possible1 = []
possibleN = []

for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        possible1.append(b)

    if b == N:
        possibleN.append(a)

product = set(possible1) & set(possibleN)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
# print(edges)
# print(1,edges[1])
first = edges[1]
# print("----")
for e in first:
    # print(e,edges[e]) 
    second = edges[e]
    if N in second:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

first = edges[1]
# print(first)
for fr in first:
    if N in edges[fr]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:

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

s_L = []

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

    if a == 1:
        s_L.append(b)
    elif b == n:
        s_L.append(a)

#print(s_L)
if len(set(s_L)) == len(s_L):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
path = dict()
for i in range(1, N+1):
  path[i] = []
for _ in range(M):
  a, b = map(int, input().split())
  path[b].append(a)
#print(path)
step = [-1] * (N+1)
step[1] = 0
for i in range(2, N+1):
  if len(path[i]) == 0: continue
  for p in path[i]:
    if step[p] == -1: continue
    if step[i] == -1:
      step[i] = step[p] + 1
    else:
      step[i] = min(step[i], step[p] + 1)
#print(step)
if step[N] == 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for i 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)
for x in g[0]:
  for y in g[x]:
    if y==n-1:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())
from_1 = np.zeros(n+1, dtype=np.int)
to_n = np.zeros(n+1, dtype=np.int)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b] = 1
    elif b == n:
        to_n[a] = 1

print('IMPOSSIBLE') if np.sum(from_1*to_n) == 0 else print('POSSIBLE')

Submission status: Accepted

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


def solve():
    N, M = map(int, rl().split())
    graph = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].add(b)
        graph[b].add(a)
    
    for child in graph[0]:
        if N - 1 in graph[child]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def solve():
    N, M = map(int, rl().split())
    graph = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].add(b)
        graph[b].add(a)
    
    for child in graph[0]:
        if N - 1 in graph[child]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
start, end = [], []
for _ in range(m):
    t1, t2 = map(int, input().split())
    if t1==1:
        start.append(t2)
    if t2==n:
        end.append(t1)

start, end = set(start), set(end)
if len(start)+len(end)==len(start | end):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

A = []
B = []

for _ in range(M):
    a,b = map(int, input().split())
    if a == 1: A.append(b)
    elif b == N: B.append(a)

B.sort()
for a in A:
    if bisect.bisect_left(B, a) < len(B) and B[bisect.bisect_left(B, a)]==a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

f, s = [],[]

for i in range(m):
    if l[i][0] == 1:
        f += [l[i][1]]
    if l[i][1] == n:
        s += [l[i][0]]

print('POSSIBLE') if set(f) & set(s) else print('IMPOSSIBLE')

Submission status: Accepted

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

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

ans = 'IMPOSSIBLE'
for x in root[n]:
  if 1 in root[x]:
    ans = 'POSSIBLE'
    break

print(ans)

Submission status: Accepted

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

boat_dict = {}

for boat in range(M):
    a, b = [int(i) for i in input().split()]
    boat_dict.setdefault(a, [])
    boat_dict[a].append(b)
        
flag = False

for i in boat_dict[1]:
    if i in boat_dict.keys():
        if N in boat_dict[i]:
            flag = True
            break

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

Submission status: Accepted

Solution code:
N, M, *A = map(int, open(0).read().split())
A = [(A[i], A[i+1]) for i in range(0, M*2, 2)]
E = [[] for _ in range(N)]
for a, b in A:
    a -= 1; b -= 1
    E[a].append(b)
    E[b].append(a)

def search(d=2, v=0, g=N-1):
    if d == 0:
        if v == g:
            return True
        else:
            return False

    for to in E[v]:
        if search(d-1, to, g):
            return True
    return False

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
to=[]
fr=[]
for _ in range(M):
  A,B=map(int,input().split())
  if A==1:
    to.append(B)
  if B==N:
    fr.append(A)
print('POSSIBLE' if len(set(to) & set(fr)) else 'IMPOSSIBLE')

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
start = []
goal = []
flag = False
for x in range(M):
    if ab[x][0] == 1:
        start.append(ab[x][1])

    if ab[x][1] == N:
        goal.append(ab[x][0])

start_goal = set(start) & set(goal)

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

Submission status: Accepted

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

start = [x[1] for x in ab if x[0] == 1]
goal = [x[0] for x in ab if x[1] == n]

ans = "IMPOSSIBLE"

if len(set(start) & set(goal)) > 0:
    ans = "POSSIBLE"

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = set()
r = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l.add(b)
    if b == n:
        r.add(a)
for x in l:
    if x in r:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

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

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

for i, j in zip(first, second):
    if i and j:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for j in d[1]:
    if N in d[j]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for i,j in list(d.items()):
    if i!=1:
        continue
    for k in j:
        if N in d[k]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
arr=[[] for i in range(n)]
for i in range(m):
    x,y=mii()
    arr[x-1].append(y-1)
chk=False

for i in arr[0]:
    if n-1 in arr[i]:
        print("POSSIBLE")

        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from collections import defaultdict

N,M=map(int,input().split())
d=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    d[a].add(b)
    d[b].add(a)

for i in d[1]:
    if N in d[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import numpy as np
N, M = input().split()
N = int(N)
M = int(M)

# 2 boat
boat = 2
ab = np.zeros(M)
ab1 = []
abN = []
ok = "IMPOSSIBLE"
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ab1.append(b)
    elif b == N:
        abN.append(a)
if len(set(abN) & set(ab1))>=1:
    ok = "POSSIBLE"
print(ok)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
scan=[]
gcan=[]
flag=0
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        scan.append(b)
    if b==N:
        gcan.append(a)
if set(scan)&set(gcan):
    flag=1
if flag==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
canMove = [[] for _ in range(N+1)]
for m in range(M):
  a, b = map(int, input().split())
  canMove[a].append(b)

for key in canMove[1]:
  if N in canMove[key]:
    print('POSSIBLE')
    sys.exit()

print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ship=[list(map(int,input().split())) for _ in range(M)]
port1=[]
port2=[]
for i in range(M):
    if ship[i][0]==1:
        port1.append(ship[i][1])
    if ship[i][1]==N:
        port2.append(ship[i][0])

port1=set(port1)
port2=set(port2)
if len(port1&port2)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

for a, b in path:
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)

for i in range(len(graph[0])):
	a = sorted(graph[graph[0][i]])
	if a[len(a) - 1] == N - 1:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

# from heapq import heappush, heappop, heapify
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

graph = defaultdict(list)
# tree = UnionFind(N)
for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

# for a in graph[a-1]:
    # for b in graph[b-1]:
s = set(graph[0]) & set(graph[N-1])
# print(set(graph[0]))
# print(set(graph[N-1]))

if not s:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


#     tree.union(a-1, b-1)

# if tree.find(0) == tree.find(N-1):
#     print("POSSIBLE")
# else:
#     print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 10 15:45:44 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N, M = na()
ab = nan(M)

G = [[] for _ in range(N)]
for i in range(M):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

def dfs(i, j, p):
    if j > 2:
        return False
    if i == N - 1 and j == 2:
        return True
    flag = False
    for k in range(len(G[i])):
        if G[i][k] == p:
            continue
        if dfs(G[i][k], j + 1, i):
            flag = True
    return flag

print("POSSIBLE" if dfs(0, 0, -1) else "IMPOSSIBLE")

Submission status: Accepted

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

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
graph = defaultdict(list)

for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)


for i in graph[0]:
	if N-1 in graph[i]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

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

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())
ab = [list(map(int,input().split())) for i in range(M)]

c = {ab[i][1] for i in range(M) if ab[i][0] == 1}
d = {ab[i][0] for i in range(M) if ab[i][1] == N}

if c & d :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Submission status: Accepted

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

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

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import collections
n, m = map(int, input().split())
c = 0
B = []
C = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        B.append(b)
    elif b == n:
        B.append(a)
C = collections.Counter(B)
for i in C:
    if C[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(m)])
relaypoint = []
for i in range(m):
  if ab[i][0] == 1:
    relaypoint.append(ab[i][1])
  else:
    break
ab.sort(key = lambda ab:ab[1],reverse = True)
relaypoint = set(relaypoint)
x = len(relaypoint)
j = 0
flag = 0
while(ab[j][1] == n):
  if ab[j][0] in relaypoint:
    flag = 1
  j += 1
if flag == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    Ton, Fr1 = set(), set()
    for _ in range(m):
        a, b = map(int, input().split())
        if b==n:
            Ton.add(a)
        if a==1:
            Fr1.add(b)

    print('POSSIBLE' if Ton&Fr1 else 'IMPOSSIBLE')

main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = {}
for _ in range(m):
    a_, b_ = map(str, input().split())
    ab.setdefault(a_, []).append(b_)
r = "IMPOSSIBLE"
if "1" in ab.keys():
    for i in ab["1"]:
        if i not in ab.keys():
            continue
        if str(n) in ab[i]:
            r = "POSSIBLE"
            break
print(r)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [[] for i in range(N)]
 
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    
#スタートは1なのでedges[1]をみる
for i in edges[1]:
    #edges[1]のつながり先にNがあるかどうか
    if N in edges[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

r = [[] for _ in range(n)]
for a, b in ab:
    r[a-1].append(b-1)
    r[b-1].append(a-1)

for i in r[0]:
    if n-1 in r[i]:
        print("POSSIBLE")
        exit()
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())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

for g in G:
    island_1=False
    island_n=False
    for gg in g:
        if gg==0:
            island_1=True
        if gg==n-1:
            island_n=True
    if island_1==True and island_n==True: 
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

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

for i in edges[1]:
  if N in edges[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Accepted

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

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

for i in edges[0]:
  if N-1 in edges[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")