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: Time Limit Exceeded

Solution code:
nm = input().split(' ')
n = int(nm[0])
m = int(nm [1])
ans  = 'IMPOSSIBLE'
mass = []
for i in range(m):
    mass += [input().split(' ' )]

fi = []
se = []
for i in mass:

    if i[0] == '1' or i[1] == '1':
       fi.append(i)
    if i[0] == str(n) or i[1] == str(n):
        se.append(i)
ff = []
for f in fi:
    for s in se:
        ff.append(f[0])
        ff.append(f[1])
        ff.append(s[1])
        ff.append(s[0])
        if len(set(ff)) == 3: 
        
            ans  = 'POSSIBLE'
            break
        ff = []

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
des = []
first = []
a = 1 ###IMPOSSIBLEフラグ
for i in range(0, m):
	des.append(list(map(int, input().split())))
###ここまで入力
###以下出力
for i in des:
	if i[0] == 1:
		first.append(i[1])
###以上1から行ける場所をfirstに格納
for i in des:
	if first.count(i[0]):
		if i[1] == n:
			print('POSSIBLE')
			a = 0
			break

if a:
	print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

ab_list.sort()

start_list = list(filter(lambda x: x[0] == 1, ab_list))

res = False

while not res:
    for start in start_list:
        if start[1] == N:
            res = True
    for start in start_list:
        for ab in list(filter(lambda x: x[0] == start[1], ab_list)):
            if ab[1] == N:
                res = True

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

Submission status: Time Limit Exceeded

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

ships = []
N, M = [int(x) for x in input().split()]
for i in range(M):
    ships.append([int(x) for x in input().split()])

from_1 = [ship[1] for ship in ships if ship[0] == 1]
to_N = [ship[0] for ship in ships if ship[1] == N]

for land in from_1:
    if land in to_N:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(M))

    flag = 0
    for i in range(1, N):
        for a, b in A:
            if a == 1 and b == i:
                flag += 1
            elif a == i and b == N:
                flag += 1

        if flag == 2:
            ans = 'POSSIBLE'
            break
        else:
            flag = 0
    else:
        ans = 'IMPOSSIBLE'

    print(ans)

main()

Submission status: Time Limit Exceeded

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

ab_list.sort()

start_list = list(filter(lambda x: x[0] == 1, ab_list))

res = False

if M > 1:
    for start in start_list:
        for ab in list(filter(lambda x: x[0] == start[1], ab_list)):
            if ab[1] == N:
                res = True
else:
    for start in start_list:
        if start[1] == N:
            res = True

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

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8

mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])

a=[]
b=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    a.append(int(hyo[0]))
    b.append(int(hyo[1]))

# collect x s.t. exists (1,x)
myon=[]
# and collct y s.t. exists (y,N)
meguru=[]
for idx in range(0,M,1):
    if a[idx]==1:
        myon.append(b[idx])

    if b[idx]==N:
        meguru.append(a[idx])

ans=False
for youmu in myon:
    if youmu in meguru:
        ans=True
        break

prefix='' if ans else 'IM'
print(prefix+'POSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    if 1 in temp or N in temp:
        a.append(min(temp))
        b.append(max(temp))

M = len(a)

flag = False

index_1 = [i for i, x in enumerate(a) if x == 1]

for i in index_1:
    for j in range(M):
        if i != j and b[i] == a[j] and N == b[j]:
            print('POSSIBLE')
            flag = True
            break
if not flag:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

if len(first)==0 or len(second)==0:
	print("IMPOSSIBLE")
else:
	if any(i  in first for i in second)==True:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

for i in range(m):
    if ship[i][0] == 1:
        for j in range(m):
            if ship[i][1] == ship[j][0] and ship[j][1] == n or ship[i][1] == ship[j][1] and ship[j][0] == n:
                print("POSSIBLE")
                exit()
    elif ship[i][1] == 1:
        for j in range(m):
            if ship[i][0] == ship[j][0] and ship[j][1] == n or ship[i][0] == ship[j][1] and ship[j][0] == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
flag=0
for i in range(M):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
for j in range(M):
    for k in range(M):
        if (b[j]==a[k]) and (a[j]==1) and (b[k]==N):
            flag += 1
        else:
            pass
if flag>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

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

    if a == 1:
        first_dest_list.append(b)
    elif b == 1:
        first_dest_list.append(a)

    pair_list.append((a, b))


len_first_dest = len(first_dest_list)
result = 'IMPOSSIBLE'
for first_dest in first_dest_list:
    for i in range(M):
        if first_dest in pair_list[i] and N in pair_list[i]:
            result = 'POSSIBLE'
            break
    if result == 'POSSIBLE':
        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y)
	elif int(y[1])==N:
		second.append(y)
	i+=1

if len(first)==0 or len(second)==0:
	print("IMPOSSIBLE")
else:
	i=0
	check=0
	while i<len(first):
		j=0
		while j<len(second):
			k=first[i]
			l=second[j]
			if k[1]==l[0]:
				print("POSSIBLE")
				check=1
				break
			else:
				j+=1
		i+=1
	else:
		if check==0:
			print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())
routes = []
for i in range(M):
    a, b = map(int, input().split())
    routes.append([a, b])
m = []
for r in routes:
    if r[0] == 1:
        m.append(r[1])
for r in routes:
    if r[0] in m:
        if r[1] == N:
            print('POSSIBLE')
            sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = list(map(int, input().split()))
a_list1 = []
b_list1 = []
a_list2 = []
b_list2 = []

for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        a_list1.append(a)
        b_list1.append(b)
    elif b == n:
        a_list2.append(a)
        b_list2.append(b)

for i in range(len(a_list1)):
    for j in range(len(a_list2)):
        if b_list1[i] == a_list2[j]:
            print('POSSIBLE')
            sys.exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

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

p1 = []
p2 = []
def solve():
    for i in range(M):
        a,b = map(int, input().split())
        if a == 1:
            p1.append(b)
        elif b == N:
            p2.append(a)
    for p in p1:
        if p in p2: return True
    return False

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = []
e = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1 and b not in s:
        s.append(b)
    elif b == n and a not in e:
        e.append(a)
if len(set(s) & set(e)) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split())
a = [map(int, raw_input().split()) for _ in range(M)]

flag = False

for i in range(M):
    if a[i][0] == 1:
        for j in range(M):
            if i != j and a[i][1] in a[j] and N in a[j]:
                print('POSSIBLE')
                flag = True
                break
    elif a[i][1] == 1:
        for j in range(M):
            if i != j and a[i][0] in a[j] and N in a[j]:
                print('POSSIBLE')
                flag = True
                break
if not flag:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
S = []
from1 = []
fromN = []
ans = "IMPOSSIBLE"
for i in range(M):
	S.append([int(x) for x in input().split()])
	if S[i][0] == 1:
		from1.append(S[i][1])
	if S[i][1] == N:
		fromN.append(S[i][0])

for x in from1:
	if x in fromN:
		ans = "POSSIBLE"

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(M):
	if c[i][0] == 1:
		for j in range(M):
			if c[j][0] == c[i][1]:
				if c[j][1] == N:
					print('POSSIBLE')
					exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m = (int(i) for i in input().split())
abstart=[]
abgoal=[]
for i in range(0,m):
    inp=[int(i) for i in input().split()]
    if inp[0]==1:
        abstart.append(inp[1])
    elif inp[1]==n:
        abgoal.append(inp[0])

for st in abstart:
    for go in abgoal:
        if st == go:
            print('POSSIBLE')
            sys.exit()
print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
b=[]
flag=0
for i in range(M):
    c,d = map(int,input().split())
    a.append(c)
    b.append(d)
for j in range(M):
    if a[j]==1:
        for k in range(M):
            if a[k]==b[j]:
                if b[k]==N:
                    flag += 1
                else:
                    pass
            else:
                pass
    else:
        pass
if flag>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
[r,s] = [int(i) for i in input().split()]
st = []
gl = []
for i in range(s):
 t = [int(i) for i in input().split()]
 if t[0]==1:
  st.append(t[1])
 elif t[1] == r:
  gl.append(t[0])
t = False
if len(st)<len(gl):
 for i in st:
  if i in gl:
   t = True
   break
else:
 for i in st:
  if i in gl:
   t = True
   break

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

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = list(map(int, input().split()))
a_list = []
b_list = []
for i in range(m):
    a, b = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
ab = zip(a_list,b_list)

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

ab = zip(a_list,b_list)
for a, b in ab:
    if a in cand_b and b == n:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = []
e = []
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.append(b)
    elif b == n:
        e.append(a)
if len(s) != 0 and len(e) != 0:
    for i in s:
        if i in e:
            ans = 'POSSIBLE'
print(ans)

Submission status: Time Limit Exceeded

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

flag = 0
for n in range(2,N+1):
    if [1,n] in ships and [n,N] in ships:
        print("POSSIBLE")
        flag=1
        break

if flag==0:
    print("IMPOSSIBLE")

Submission status: Time Limit Exceeded

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

m_1=[]
m_N=[]
for _ in range(M):
    a,b=map(int,raw_input().split(' '))
    if a==1 and not a in m_1:
        m_1.append(b)
    if b==N and not a in m_N:
        m_N.append(a)

if len(set(m_1)-set(m_N))==len(set(m_1)):
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

Submission status: Time Limit Exceeded

Solution code:
[r,s] = [int(i) for i in input().split()]
st = []
gl = []
for i in range(s):
 t = [int(i) for i in input().split()]
 if t[0]==1:
  st.append(t[1])
 elif t[1] == r:
  gl.append(t[0])
t = False
for i in st:
 if i in gl:
  t = True
  break
if t:
 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)]
res = []
for a, b in AB:
    if a == 1:
        res.append(b)
    if b == N:
        res.append(a)
print('IMPOSSIBLE' if len(res) == len(set(res)) else 'POSSIBLE')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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)

ok = False
for v in G[0]:
    s = G[v]
    if n-1 in s:
        ok = True

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 27 02:05:32 2020

@author: liang
"""

N, M = map(int, input().split())
first = list()
second = set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        first.append(b)
    if b == N:
        second.add(a)
        
for a in first:
    if a in second:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import heapq
import sys
input = lambda :sys.stdin.readline().rstrip()

def INPUT(mode=int):
    return list(map(mode, input().split()))

def Dijkstra_heap(s, edge):
    # 始点sから各頂点への最短距離#始点sから各頂点への最短距離
    d = [10**20] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    for i, j in edge[s]:
        heapq.heappush(edgelist, i+j*(10**6))
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v = minedge % (10**6)
        # まだ使われてない頂点の中から最小の距離のものを探す
        if used[v]: continue
        d[v] = minedge // (10**6)
        used[v] = True
        for e in edge[v]:
            if not used[e[0]]:
                heapq.heappush(edgelist, e[0]+(e[1]+d[v]) * (10**6))
    return d

n, m = INPUT()
AB = [INPUT() for _ in range(m)]
edge = [[] for _ in range(n)]
for a, b in AB:
    a -= 1
    b -= 1
    edge[a].append((b, 1))
    edge[b].append((a, 1))

dist = Dijkstra_heap(0, edge)
if dist[-1] <= 2:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

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

if len(set(A) & set(B)) != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

re = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int, input().split())
  re[a].append(b)
  re[b].append(a)
  
reach = [0]*(n+1)
reach[1] = 1
for i in re[1]:
  if reach[i] == 0:
    for j in re[i]:
      reach[j] = 1

if reach[n] == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# C - Cat Snuke and a Voyage
def main():
    n, m = map(int, input().split())
    li = [0]*200001

    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            if li[b] == 0:
                li[b] = 1
            else:
                print('POSSIBLE')
                exit()
        if b == n:
            if li[a] == 0:
                li[a] = 1
            else:
                print('POSSIBLE')
                exit()
    else:
        print('IMPOSSIBLE')

if __name__ ==  "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
li = [0]*200001
s = "IMPOSSIBLE"
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        if li[b] == 0:
            li[b] = 1
        else:
            s = "POSSIBLE"
    
    if b == n:
        if li[a] == 0:
            li[a] = 1
        else:
            s = "POSSIBLE"

print(s)

Submission status: Accepted

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

c = []
d = []

for i in range(M):
    if a[i] == 1:
        c.append(b[i])

for i in range(M):
    if b[i] == N:
        d.append(a[i])

e = set(c) & set(d)

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

Submission status: Accepted

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

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

K = [-1] * N
def dfs(now,time):
    K[now] = time
    for i in ki[now]:
        time += 1
        dfs(i,time)
        time -= 1

dfs(0,0)
print('POSSIBLE' if K[N-1] == 2 else 'IMPOSSIBLE')

Submission status: Accepted

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

# n, m = 3, 2
# a = [[1, 2], [2, 3]]

pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

if set(pot_starts).intersection(set(pot_ends)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

# n, m = 3, 2
# a = [[1, 2], [2, 3]]

pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

if set(pot_starts).intersection(pot_ends):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    ans = "IMPOSSIBLE"
    list_1 = []
    list_n = []
    for i in range(m):
        if ab[i][0] == 1:
            list_1.append(ab[i][1])
        elif ab[i][1] == n:
            list_n.append(ab[i][0])
    if len(set(list_1) & set(list_n)) > 0:
        ans = "POSSIBLE"
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

N, M = [int(i) for i in input().split()]
map = {k: [] for k in range(1, N + 1)}

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


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


print('IMPOSSIBLE')

Submission status: Accepted

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

for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    a1.append(b)
  elif b == n:
    bn.append(a)
la = len(a1)
lb = len(bn)
sa = set(a1)
sb = set(bn)
if len(sa | sb) < la + lb:
  print('POSSIBLE')
  exit()
print('IMPOSSIBLE')

Submission status: Accepted

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

print('IMPOSSIBLE')

Submission status: Accepted

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

N,M = map(int,readline().split())
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
for child in G[0]:
  for gchild in G[child]:
    if gchild == N - 1:
      print("POSSIBLE")
      exit(0)
print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    ab_lst = []
    for i in range(m):
        ab_lst.append(list(map(int, input().split())))

    flag = False
    lst = []
    for i in range(m):
        a = ab_lst[i][0]
        b = ab_lst[i][1]

        if a == 1:
            lst.append(b)
    st = set(lst)

    for i in range(m):
        a = ab_lst[i][0]
        b = ab_lst[i][1]

        if b == n:
            if a in st:
                flag = True
                break

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

edge = [[] for i in range(n)]

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

possible = False
for to in edge[0]:
    if n-1 in edge[to]:
        possible = True
        break

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-09-13 15:43:14 +0900
# LastModified: 2020-09-13 15:49:14 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import deque


def main():
    N, M = map(int, input().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    Q = deque(path[1])
    flag = False
    while Q and flag is False:
        u = Q.popleft()
        for v in path[u]:
            if v == N:
                flag = True
    if flag:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setRank(self, other: 'Island') -> None:
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setRank(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    #諸島生成
    islands: Islands = Islands(N)
    #諸島間定期便生成
    for a, b in ab:
        islands[a].addConnection(islands[b])
    #bfs
    bfs(islands[1], 2)
    #出力
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.parent: 'Island' = None
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setAsRoot(self):
        self.parent = self
    
    def setParent(self, other: 'Island') -> None:
        self.parent = other
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    root.setAsRoot()
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setParent(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    #諸島生成
    islands: Islands = Islands(N)
    #諸島間定期便生成
    for a, b in ab:
        islands[a].addConnection(islands[b])
    #bfs
    bfs(islands[1], 2)
    #出力
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[list() 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)
G[0].sort()
G[N-1].sort()
i=0
j=0
while i<len(G[0]) and j<len(G[N-1]):
    if G[0][i]==G[N-1][j]:
        print("POSSIBLE")
        break
    elif G[0][i]<G[N-1][j]:
        i+=1
    else:
        j+=1
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
L.sort(key=lambda x: x[0])
funes1 = [False]*N
for a,b in L:
    if a == 1:
        funes1[b] = True
    else:
        if funes1[a]:
            if b == N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# cython: profile=True
import sys

YES = "POSSIBLE"  # type: str
NO = "IMPOSSIBLE"  # type: str


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    AB = sorted(zip(a, b))
    s = set([b for a, b in AB if a == 1])
    g = set([a for a, b in AB if b == N])
    return YES if s & g else NO

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

def test():
    import doctest
    doctest.testmod()

def perf():
    import cProfile
    cProfile.run("main()")

if __name__ == '__main__':
    #test()
    #perf()
    main()

Submission status: Accepted

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

dic = {}
for (a, b) in ab:
  if a in dic.keys():
    dic[a].append(b)
  else:
    dic[a] = [b]
  
check = False
for i in dic[1]:
  if i in dic.keys():
    for j in dic[i]:
      if j == N:
        check = True

print("POSSIBLE" if check else "IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
root_map = dict()
root_map[1] = set()
root_map[n] = set()

for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or a == n:
        root_map[a].add(b)
    if b == 1 or b == n:
        root_map[b].add(a)

if root_map[1] & root_map[n]:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
root_map = dict()
root_map[1] = set()
root_map[n] = set()

for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or a == n:
        root_map[a].add(b)
    if b == 1 or b == n:
        root_map[b].add(a)

for i in root_map[1]:
    if i in root_map[n]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
root_map = dict()
root_map[1] = set()
root_map[n] = set()

for i in range(m):
    a, b = map(int, input().split())
    if a not in root_map:
        root_map[a] = set()
        root_map[a].add(b)
    else:
        root_map[a].add(b)
    if b not in root_map:
        root_map[b] = set()
        root_map[b].add(a)
    else:
        root_map[b].add(a)

for i in root_map[1]:
    if i in root_map[n]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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