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())
r=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
ans=False
for i in range(1,n-1):
    if 0 in r[i]and (n-1) in r[i]:
        ans=True

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
p=[]
for x in range(M):
    p.append(input())
A=[]
B=[]
for x in range(M):
    a,b=map(int,p[x].split())
    A.append(a)
    B.append(b)
    
isl=[]
for x in range(N):
    isl.append(0)
for x in range(M):
    if A[x]==1:
        isl[B[x]]=1
for x in range(M):
    if B[x]==N:
        isl[A[x]]=isl[A[x]]+1

if 2 in isl:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    m = set()
    for _ in range(M):
        a, b = map(int, input().split())
        if a < b:
            m.add((a,b))
        else:
            m.add((b,a))
    for i in range(2, N):
        if (1, i) in m and (i, N) in m:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N, M = map(int, input().split(" "))
    m = set()
    for _ in range(M):
        a, b = map(int, input().split(" "))
        if a < b:
            m.add((a,b))
        else:
            m.add((b,a))
    for i in range(2, N):
        if (1, i) in m and (i, N) in m:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N, M = map(int, input().split(" "))
m = set()

for _ in range(M):
    a, b = map(int, input().split(" "))
    if a < b:
        m.add((a,b))
    else:
        m.add((b,a))


for i in range(2, N):
    if (1, i) in m and (i, N) in m:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N, M = list(map(int, input().split(" ")))
m = set()

for _ in range(M):
    a, b = list(map(int, input().split(" ")))
    if a < b:
        m.add((a,b))
    else:
        m.add((b,a))


for i in range(2, N):
    if (1, i) in m and (i, N) in m:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(" ")))
m = set()

for _ in range(M):
    a, b = list(map(int, input().split(" ")))
    if a < b:
        m.add((a,b))
    else:
        m.add((b,a))


for i in range(2, N):
    if (1, i) in m and (i, N) in m:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

N, M = map(int, raw_input().split())
start, finish = [], []
for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        start.append(b)
    elif b == N:
        finish.append(a)

if set(start) & set(finish):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'

Submission status: Accepted

Solution code:
def Q3(N, M, *arg):
    import numpy as np
    route = np.reshape(np.array(*arg), (M, 2))
    string = 'IMPOSSIBLE'
    p = [False] * N
    q = [False] * N
    for x in route:
        if x[0] == 1:
            p[x[1]] = True
        elif x[1] == N:
            q[x[0]] = True
    for i in range(N):
        if p[i] and q[i]:
            string = 'POSSIBLE'
            break
    return string

N, M = map(int, input().split())
l = [list(map(lambda x: int(x), input().split())) for i in range(M)]
l = [flatten for inner in l for flatten in inner]
print(Q3(N,M,l))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [False] * n
g = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s[b] = True
    if b == n:
        g[a] = True

ans = "IMPOSSIBLE"
for i in range(n):
    if s[i] and g[i]:
        ans = "POSSIBLE"
        break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from1 = [False] * N
toN = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from1[b] = True
    if b == N:
        toN[a] = True
msg = "IMPOSSIBLE"
for i in range(N):
    if from1[i] and toN[i]:
        msg = "POSSIBLE"
        break
print(msg)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from1 = set()
toN = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from1.add(b)
    if b == N:
        toN.add(a)
msg = "IMPOSSIBLE" if from1.isdisjoint(toN) else "POSSIBLE"
print(msg)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [list() 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 g1 in graph[0]:
    if N-1 in graph[g1]:
        print("POSSIBLE")
        break
        
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

import math

N, M = map(int, input().split())
start = [False] * N
goal = [False] * N
for i in range(M):
    a1, a2 = map(int, input().split())
    if (a1 == 1):
        start[a2 - 1] = True
    if (a2 == N):
        goal[a1 - 1] = True

def check():
    for i in range(N):
        if (start[i] & goal[i]):
            return('POSSIBLE')
    return('IMPOSSIBLE')

print(check())

Submission status: Accepted

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

toN =[]
first = []
end = False

for i in range(M):
    if S[i][1] == N:
        toN.append(S[i][0])

for i in range(M):
    if S[i][0] == 1:
        first.append(S[i][1])

toN = set(toN)
first = set(first)

if toN.intersection(first):
    print "POSSIBLE"

else:
    print "IMPOSSIBLE"

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
G = {v: set() for v in range(N+1)}
for i in range(M):
    a, b = map(int, raw_input().split())
    G[a].add(b)
    G[b].add(a)
ok = False
for v in range(N+1):
    if (1 in G[v]) and (N in G[v]):
        ok = True
        break
print "POSSIBLE" if ok else "IMPOSSIBLE"

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr1=set()
arrn=set()
for _ in range(m):
    a,b=map(int,input().split())
    if a==1 and b==n or a==n and b==1:
        print("POSSIBLE")
        exit(0)
    else:
        if a==1:
            arr1.add(b)
        elif a==n:
            arrn.add(b)
        elif b==1:
            arr1.add(a)
        elif b==n:
            arrn.add(a)
if len(arr1.intersection(arrn))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
# coding: utf-8

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

if begin_to.isdisjoint(end_from):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
start = set([])
end = set([])
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.add(a*b)
    if a == N or b == N:
        end.add(a * b / N)
flag = 0
for i in start:
    if i in end:
        print("POSSIBLE")
        flag = 1
        break
if not(flag):
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#coding: utf-8
class Scanner(object):
    """docstring for Scanner."""
    s = []
    idx = 0
    separater = ""

    def __init__(self, separater=" "):
        self.separater = separater

    def next(self):
        while self.idx >= len(self.s):
            st = input()
            while st == "":
                st = input()
            self.s = st.split(self.separater)
            self.idx = 0
        self.idx += 1
        return self.s[self.idx - 1]

    def next_int(self):
        return int(self.next())

    def next_float(self):
        return float(self.next())


sc = Scanner()
N = sc.next_int()
M = sc.next_int()
graph = []
for i in range(N):
    graph.append([])
for i in range(M):
    a = sc.next_int() - 1
    b = sc.next_int() - 1

    graph[a].append(b)
    graph[b].append(a)
successed = False

for neighbors in graph[N - 1]:
    for neighbor in graph[neighbors]:
        if neighbor == 0:
            successed = True

if successed:
    print("POSSIBLE")

else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
from sets import Set

def solve():
	n, m = map(int, raw_input().split())
	to1 = Set()
	toN = Set()

	for i in range(m):
		x, y = map(int, raw_input().split())
		if x == 1:
			to1.add(y)
		if x == n:
			toN.add(y)
		if y == 1:
			to1.add(x)
		if y == n:
			toN.add(x)

	for i in range(n):
		if i in to1 and i in toN:
			print "POSSIBLE"
			return
			
	print "IMPOSSIBLE"

solve()

Submission status: Accepted

Solution code:
def solve(n, m, a, b):
    islands = set()

    for i in range(m):
        if(a[i] == 1):
            islands.add(b[i])
        if(b[i] == 1):
            islands.add(a[i])

    for i in range(m):
        if(a[i] == n and b[i] in islands):
            return "POSSIBLE"
        if(b[i] == n and a[i] in islands):
            return "POSSIBLE"
    return "IMPOSSIBLE"

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

for i in range(m):
    (ai, bi) = map(int, input().split())
    a.append(ai)
    b.append(bi)

print(solve(n, m, a, b))

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
a = []
b = []

for i in range(M):
    c, d = map(int, input().split())
    a.append(c)
    b.append(d)

s = set()

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

for i in range(M):
    if a[i] == 1 and b[i] in s:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Submission status: Accepted

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

import sys
from collections import defaultdict

inputs = list(map(int, sys.stdin.readline().split()))

n = inputs[0]
m = inputs[1]

ai = defaultdict(list)

for i in range(m):
	inputs = list(map(int, sys.stdin.readline().split()))
	a = inputs[0]
	b = inputs[1]
	ai[a].append(b)
	ai[b].append(a)


pos = 1

for dst in ai[pos]:
	if dst == n:
		print("POSSIBLE")
		sys.exit()

	for dst2 in ai[dst]:
		if dst2 == n:
			print("POSSIBLE")
			sys.exit()

print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#!/usr/bin
# -*- coding="utf-8" -*-
c1 = []
c2 = []
q = input().split()
n = [input().split() for i in range(int(q[1]))]
 
for m in n:
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Accepted

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

startset=set(start)
endset=set(end)
if startset & endset:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
n,m = map(int, raw_input().split())
s = set()
t = set()
for _ in range(m):
    a,b = map(int, raw_input().split())
    if a == 1:
        s.add(b)
    elif b == 1:
        s.add(a)
    if a == n:
        t.add(b)
    elif b == n:
        t.add(a)
u = s.intersection(t)
if len(u) == 0:
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

Submission status: Accepted

Solution code:
# coding: utf-8


def main():
    n, m = map(int, raw_input().split())

    s = [0] * 200010
    t = [0] * 200010
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        if a == 1:
            s[b] = True
        if b == n:
            t[a] = True

    for i in xrange(1, n+1):
        if s[i] and t[i]:
            print "POSSIBLE"
            return

    print "IMPOSSIBLE"

main()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, raw_input().split(' '))
route = [map(int, raw_input().split(' ')) for _ in xrange(M)]

A = {}
for a, b in route:
    A.setdefault(a, []).append(b)
    A.setdefault(b, []).append(a)


def bfs(A, start, end):
    visited = set()
    queue = deque()
    visited.add(start)
    queue.append((start, 0))
    while len(queue) > 0:
        a, d = queue.popleft()
        if d >= 2:
            break
        for b in A[a]:
            if b == end:
                return True
            if b not in visited:
                visited.add(b)
                queue.append((b, d+1))
    return False


if bfs(A, 1, N):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().split()]
set1=[]
setn=[]
for i in [None]*M:
    ipt=[int(x) for x in input().split()]
    if 1 in ipt:
        set1 += ipt
    if N in ipt:
        setn += ipt
if set(set1) & set(setn):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys 

N,M  = map(int,input().split())
     
a = [[0 for i in range(2)] for j in range(M)]
b = [] 
c = []

for i in range(M):
  a[i][0] , a[i][1] = map(int,input().split())
  first, second = a[i][0],a[i][1]
  if first == 1:
    b.append(second)
  if second == N:
    c.append(first)

b_set = set(b)
c_set = set(c)

if list(b_set & c_set) is None or len(list(b_set & c_set)):
  res = ('POSSIBLE')
else:
  res = ('IMPOSSIBLE')

print(res)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


# sys.stdin = open('c1.in')


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


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


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
    n, m = read_int_list()
    c = Counter()
    for i in range(m):
        a, b = read_int_list()
        if a == 1:
            c[b] += 1
        if b == n:
            c[a] += 1

    if 2 in c.values():
        return 'POSSIBLE'
    return 'IMPOSSIBLE'


res = solve()
print(res)

Submission status: Accepted

Solution code:
# coding: utf-8

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

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

res = "IMPOSSIBLE"
for i in range(2, N):
    if 1 in graph[i] and N in graph[i]:
        res = "POSSIBLE"

print(res)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

# sys.stdin = open('c1.in')


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


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


def read_int():
    return int(input())


def read_str():
    return input()


n, m = read_int_list()
c = Counter()

for i in range(m):
    a, b = read_int_list()
    if a == 1:
        c[b] += 1
    if b == n:
        c[a] += 1

res = 'IMPOSSIBLE'
if 2 in c.values():
    res = 'POSSIBLE'
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

a = list(map((int), input().split(' ')))
N, M = a[0], a[1]
 
first = []
second = []
 
for i in range(M):
    
    b = list(map((int),input().split(' ')))
    start, end = b[0], b[1]
    
    if start == 1:
        first.append(end)
    if end == N:
        second.append(start)
        
first_set = set(first)
second_set = set(second)
 
matched_l = list(first_set & second_set)
 
if matched_l is None or len(matched_l) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

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

a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
        
in2_set=set(in2)
out2_set=set(out2)
matched_list=list(in2_set & out2_set)
#print(matched_list)
if len(matched_list)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !

a = list(map((int), input().split(' ')))
N, M = a[0], a[1]

first = []
second = []

for i in range(M):
    
    b = list(map((int),input().split(' ')))
    start, end = b[0], b[1]
    
    if start == 1:
        first.append(end)
    if end == N:
        second.append(start)
        
first_set = set(first)
second_set = set(second)

matched_l = list(first_set & second_set)

if matched_l is None or len(matched_l) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

Solution code:
a=input()
b=a.split(" ")
N=int(b[0])
M=int(b[1])
in2=[]
out2=[]
for i in range(M):
    c=input()
    d=c.split(" ")
    in1=int(d[0])
    out=int(d[1])
    if in1==1:
        in2.append(str(out))
    elif out==N:
        out2.append(str(in1))
        
in2_set=set(in2)
out2_set=set(out2)
matched_list=list(in2_set & out2_set)
#print(matched_list)
if len(matched_list)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Accepted

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

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

for destination in origindestination[1]:
    if N in origindestination[destination]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
for i in range(M):
    x,y=[int(i) for i in input().split()]
    if x==1 :
        c.append(y)
    if y==N:
        c.append(x)
if len(c)==len(set(c)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

s = []
t = []

for i in range(M):
    if a[i] == 1:
        s.append(b[i])
    elif b[i] == N:
        t.append(a[i])

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

Submission status: Accepted

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

Submission status: Accepted

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


N,M=list(map(int,raw_input().split()))
#print N
#print M

adj=[[] for i in range(N+1)]

#隣接リスト
for i in range(M):
	x,y=list(map(int,raw_input().split()))
	#if x==1 and y==N:
	#	continue
	adj[x].append(y)
	adj[y].append(x)

#print adj

#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist=(N+1)*[0]

#先頭から深さ優先探索
S.append(1)
while len(S) != 0:
	#print S
	v=S.pop()
	#print "v:::"+str(v)
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				if dist[u] == 0:
					dist[u]=dist[v]+1
					#print S
					#print dist

#print dist

if dist[N]==2:
	print "POSSIBLE"
else:
	print "IMPOSSIBLE"

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ship_1 = [False]*(n+1)
ship_n = [False]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship_1[b] = True
    elif b == n:
        ship_n[a] = True

for i in range(len(ship_1)):
    if ship_1[i] and ship_n[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Accepted

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

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
import sys
from collections import Counter

# sys.stdin = open('c1.in')


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


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


def read_int():
    return int(input())


def read_str():
    return input()


n, m = read_int_list()

a = [0] * m
b = [0] * m

for i in range(m):
    a[i], b[i] = read_int_list()

c = Counter()
for i in range(m):
    if a[i] == 1:
        c[b[i]] += 1
    if b[i] == n:
        c[a[i]] += 1

res = 'IMPOSSIBLE'
for i, v in c.items():
    if v == 2:
        res = 'POSSIBLE'
print(res)

Submission status: Accepted

Solution code:
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Accepted

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

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

flag=False
for i in ship[1]:
    if n in ship[i]: flag=True; break

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

Submission status: Accepted

Solution code:
import sys
l = list(map(int, input().split(' ')))
N = l[0]
N_ = l[0] + 1
M = l[1]
y = []
u = set()

for i in range(M):
    k = list(map(int, input().split()))
    a = k[0]
    b = k[1]
    if (a == 1):
        y.append(b)
    elif (b == N):
        u.add(a)

for i in y:
    if (i in u):
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
a=[]
b={}
n,m = map(int,input().split())
for _ in range(m):
    i,j = map(int,input().split())
    if i==1:
        a.append(j)
    elif j==n:
        b[i]=1
for i in a:
    if i in b:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
N,M=list(map(int,input().strip().split(' ')))
graph=[[] for i in range(N)]
for _ in range(M):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    graph[a]+=[b]
    graph[b]+=[a]
from collections import deque

q=deque([0])

visit=[0]*N
level=[0 for i in range(N)]
level[N-1]=3
parent=[-1]*N
while q:
    v=q.popleft()
    visit[v]=1
    for adj in graph[v]:
        if adj!=parent[v] and visit[adj]==0:
            parent[adj]=v
            visit[adj]=1
            q+=[adj]
            level[adj]=level[v]+1
if level[N-1]<=2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
   N,M = map(int,input().split())
   Set = set()
   for i in range(M):
      a,b = map(int,input().split())
      Set.add((a,b))
      Set.add((b,a))                        #condition
   for j in range(2,N):
      if (1,j) in Set and (j,N) in Set:
         print("POSSIBLE")
         return
   print("IMPOSSIBLE")

main()

Submission status: Accepted

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])-1)
    b.append(int(hyo[1])-1)

# collect x s.t. exists (1,x)
myon_tbl=[False]*N
# and collct y s.t. exists (y,N)
meguru_tbl=[False]*N
for idx in range(0,M,1):
    if a[idx]==0:
        myon_tbl[b[idx]]=True

    if b[idx]==N-1:
        meguru_tbl[a[idx]]=True

ans=False
for idx in range(0,N,1):
    if myon_tbl[idx] and meguru_tbl[idx]:
        ans=True
        break

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

Submission status: Accepted

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

if any(list(set(a) & set(b))):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Accepted

Solution code:
d = {}

def bfs(graph, start, goal): 
#These variables define the visited set (to make sure that the program doesn’t go through the same nodes twice) a queue to make sure that the node seen next is visted first. 
 
    visited, queue = set(), [start] 
    pathsTo = {} 
    pathsTo[start] = [start] 
    index = 0
    lenqueue = 1
# Ensuring that the queue is not empty at any point in time. 
    while index < lenqueue: 
# Getting the next node and getting rid of the node in the front of the queue. 
        vertex = queue[index] 
        if vertex not in visited: 
            visited.add(vertex) 
 
 
            # Going through each element in the adjacency list and making sure that it hasn’t been visited, and that it is not in the same path. 
            for newVertex in (graph[vertex]): 
                if newVertex not in visited: 
                    if newVertex not in pathsTo: 
                        pathsTo[newVertex] = list() 
 
                    for path in pathsTo[vertex]: 
                        pathsTo[newVertex].append(str(path)+"->"+str(newVertex)) 
                    queue.append(newVertex)
                    lenqueue += 1
        index += 1
    # Return the paths toward the goal.
    if goal not in pathsTo.keys():
        return ["8384793->8->4->7-> 9 8 23748"]
    return pathsTo[goal] 

N, M = map(int,input().split())
for i in range(M):
    a,b = map(int,input().split())
    if a not in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)

    if b not in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)

dist = len(bfs(d,1,N)[0].split("->")) - 1
if dist <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

Solution code:
#!/usr/bin/python

import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M = map(lambda x: int(x), line.split(" ", 2))

        services_1 = {}
        services_n = []
        for i in xrange(M):
            a, b = map(lambda x: int(x), sys.stdin.readline().split(" ", 2))
            if a == 1:
                services_1[b] = True
            if b == N:
                services_n.append(a)

        if 1 in services_n:
            print("POSSIBLE")

        result = "IMPOSSIBLE"
        for service in services_n:
            if service == 1 or service in services_1:
                result = "POSSIBLE"
                break
        print result                

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

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

first=set(first)
second=set(second)
if len(first.intersection(second))>0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Submission status: Accepted

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

for i in range(M):
    if a[i] == 1:
        ikeru[b[i]] = 1
ikeru_2 = [0]*(N+1)
for i in range(M):
    if ikeru[a[i]] == 1:
        ikeru_2[b[i]] = 1
if ikeru_2[N] == 1 or ikeru[N] == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

    if M == 1:
        print('IMPOSSIBLE')
        return

    relay = []
    for a, b in A:
        if a == 1:
            relay.append(b)
        elif b == N:
            relay.append(a)

    if len(relay) > len(set(relay)):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

main()

Submission status: Accepted

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

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 = set([ship[1] for ship in ships if ship[0] == 1])
to_N = set([ship[0] for ship in ships if ship[1] == N])

if from_1.intersection(to_N):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Accepted

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

import sys

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

from_to = {}
for i in range(M):
    line = input()
    line = line.rstrip()
    ai, bi = map(int, line.split())

    l = from_to.get(ai, list())
    l.append(bi)
    from_to[ai] = l

#print(from_to)

next_lands = from_to.get(1, list())
if not next_lands:
    print('IMPOSSIBLE')

for n in next_lands:
    goals = from_to.get(n, list())
    if N in goals:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')