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: Wrong Answer

Solution code:
N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
Q = []
q = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        p = P[i][1]
        if q < 0:
            q = i-1
        for j in range(q, M):
            if P[j][0] == p:
                if P[j][1] == N:
                    ans = ("POSSIBLE")
                    break
            elif P[j][0] > p:
                q = j - 1
                break
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
Q = []
q = -1
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        p = P[i][1]
        if q < 0:
            q = i-1
        for j in range(q, M):
            if P[j][0] == p:
                if P[j][1] == N:
                    ans = ("POSSIBLE")
                    break
            elif P[j][0] > p:
                q = j
                break
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
P = [list(map(int,input().split())) for _ in range(M)]
P.sort()
Q = []
s = 0
ans = ("IMPOSSIBLE")
for i in range (M):
    if P[i][0] == 1:
        Q.append(P[i][1])
    else:
        s = i - 1
        break
if s > 0:
    for j in range(s, M):
        if P[j][1] == N:
            if P[j][0] in Q:
                ans = ("POSSIBLE")
print(ans)

Submission status: Wrong Answer

Solution code:

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

ok1 = [False] * n
ok2 = [False] * n

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    if a == 0:
        ok1[b] = True
    if b == n - 1:
        ok2[b] = True

for m in range(n):
    if ok1[m] and ok2[m]:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[]
k=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        s.append(b)
    if b==n:
        k.append(1)
s_i=set(s)
k_i=set(k)
for _ in s_i:
    if _ in k_i:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            graph = [[None] * N] * N
            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                graph[a - 1][b - 1], graph[b - 1][a - 1] = 1, 1

            edges_from1 = graph[0].count(1)
            edges_fromN = graph[N - 1].count(1)
            if not edges_from1 or not edges_fromN:
                print("IMPOSSIBLE")
                break

            if edges_from1 < edges_fromN:
                start_node = 0
                goal_node = N - 1
            elif edges_fromN < edges_from1:
                start_node = N - 1
                goal_node = 0
            else:
                start_node = 0
                goal_node = N - 1

            for j in range(N):
                if graph[start_node][j] == 1:
                    if graph[j][goal_node] == 1:
                        print("POSSIBLE")
                        raise EndLoop

            print("IMPOSSIBLE")
        except:
            break


solve()

Submission status: Wrong Answer

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

a = []

for i in range(m):
    if ab[i][0] == '1':
        a += ab[i][1]

for i in range(m):
    if ab[i][1] == str(n) and ab[i][0] in a:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

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

ans = "IMPOSSIBLE"

ls = {}
f = [False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    ls[a-1] = b-1
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
    if a-1 == 0:
        f[a-1] = True

for m in range(M):
    if ans == "POSSIBLE":
        break
    if f[m] and ls[m] in ls and  ls[ls[m]] == N-1 :
        ans = "POSSIBLE"

print(ans)

Submission status: Wrong Answer

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

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

ans = "IMPOSSIBLE"

ls = {}
f = [False]*M

for m in range(M):
    a,b = map(int,(input().split()))
    ls[a-1] = b-1
    
    if a-1 == 0 and b-1 == N-1:
        ans = "POSSIBLE"
        break
    if a-1 == 0:
        f[a-1] = True

for m in range(M):
    if ans == "POSSIBLE":
        break
    if f[m] and ls[m] in ls and  ls[ls[m]] == N-1 :
        ans = "POSSIBLE"

print(ans)

Submission status: Wrong Answer

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

ans = "IMPOSSIBLE"

ls = [[] for m in range(M+1)]
for m in range(M):
    a,b = map(int,(input().split()))
    ls[m].append(a)
    ls[m].append(b)
    
    if a == 1 and b == N:
        ans = "POSSIBLE"
        break
    if a == 1:
        ls[m].append("P")
    else:
        ls[m].append("I")

for m in range(M):
    if ls[m][2] == "P" and ls[m][1] == N:
        ans = "POSSIBLE"

print(ans)

Submission status: Wrong Answer

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

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

ans = "IMPOSSIBLE"

for m in range(M):
    if ls[m][0] == 1 and ls[m][1] == N-1 :
        ans = "POSSIBLE"
        break
    elif ls[m][0] == 1:
        ls[m].append("P")
    else:
        ls[m].append("I")

if ans != "POSSIBLE":
    for m in range(M):
        if ls[m][2] == "P" and ls[m][1] == N-1:
            ans = "POSSIBLE"

print(ans)

Submission status: Wrong Answer

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

for i in range(0, N):
    c = c + [0]

for i in range(0, M):
    a, b = map(int, input().split(" "))
    if (a == 1) and (c[b] % 10 == 0):
        c[b] = c[b] + 1
    elif (b == N) and (c[a] < 10):
        c[a] = c[a] + 10

print(c)

if 11 in c:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

for i in range(0, N):
    c = c + [0]

for i in range(0, M):
    a, b = map(int, input().split(" "))
    if (a == 1) and (c[b] % 10 == 1):
        c[b] = c[b] + 1
    elif (b == N) and (c[a] < 10):
        c[a] = c[a] + 10

if 11 in c:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = list(filter(lambda x: x<b, c)) + [b] + list(filter(lambda x: x>b, c))
    elif b == N:
        d = list(filter(lambda x: x<a, d)) + [a] + list(filter(lambda x: x>a, d))

Submission status: Wrong Answer

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == N:
        d = d + [a]

Submission status: Wrong Answer

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

c = []
d = []
for i in range(0, M):
    a, b = map(int, input().split(" "))
    if a == 1:
        c = c + [b]
    elif b == 1:
        c = c + [a]
    elif a == N:
        d = d + [b]
    elif b == N:
        d = d + [a]

for i in c:
    if i in d:
        print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

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

for i in c:
    if i in d:
        print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

a=[]
b=[]
for i in range(0, M):
    a_tmp, b_tmp = map(int, input().split(" "))
    a = a+[a_tmp]
    b = b+[b_tmp]

c=[]
for i in range(0, M):
    if a[i] == 1:
        c = c + [b[i]]

print("POSSIBLE")

Submission status: Wrong Answer

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)

f=0
for x in range(M):
    if A[x]==1:
        for y in range(M):
            if A[y]==B[x]:
                if B[y]==N:
                    print("POSSIBLE")
                else:
                    f=f+1/M
            else:
                f=f+1/M
    else:
        f=f+1
if f==M:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

for x in range(M):
    p.append(input())

f=0
for x in range(M):
    if "1 %s" % x in p:
        if "%s N" % x in p:
            print("POSSIBLE")
        else:
            f=f+1
    else:
        f=f+1
if f==M:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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:
        print(x[0],x[1])
        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'
    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: Wrong Answer

Solution code:
import math

def solve(n, m, a, b):
    islands = []

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

    for i in range(m):
        if(a[i] == m and b[i] in islands):
            return "POSSIBLE"
        if(b[i] == m 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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys

def main():

    n, m = sys.stdin.readline().strip().split(" ")

    n = int(n)
    m = int(m)
    vis = list(map(lambda _: False, list(range(m+1))))

    ans = False

    for i in range(m):
        a, b = sys.stdin.readline().strip().split(" ")
        a = int(a)
        b = int(b)

        if (a == 1):
            if (vis[b] == True):
                ans = True
            else:
                vis[b] = True
        elif (b == n):
            if (vis[a] == True):
                    ans = True
            else:
                    vis[a] = True;



    if (not ans):
        sys.stdout.write("IMPOSSIBLE\n")

    else:
        sys.stdout.write("POSSIBLE\n")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys

def main():

    n, m = sys.stdin.readline().strip().split(" ")

    n = int(n)
    m = int(m)
    vis = list(map(lambda _: False, list(range(m+1))))

    ans = False

    for i in range(m):
        a, b = sys.stdin.readline().strip().split(" ")
        a = int(a)
        b = int(b)

        if (a == 1):
            if (vis[b] == True):
                ans = True
            else:
                vis[b] = True
        elif (b == n):
            if (vis[a] == True):
                    ans = True
            else:
                    vis[a] = True;



    if (not ans):
        sys.stdout.writelines("IMPOSSIBLE")

    else:
        sys.stdout.writelines("POSSIBLE")

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys

def main():

    n, m = sys.stdin.readline().strip().split(" ")

    n = int(n)
    m = int(m)
    vis = list(map(lambda _: False, list(range(m+1))))

    ans = False

    for i in range(m):
        a, b = sys.stdin.readline().strip().split(" ")
        a = int(a)
        b = int(b)

        if (a == 1):
            if (vis[b] == True):
                ans = True
            else:
                vis[b] = True
        elif (b == n):
            if (vis[a] == True):
                    ans = True
            else:
                    vis[a] = True;
                
        

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

Submission status: Wrong Answer

Solution code:
import sys

def main():

    n = sys.stdin.readline().strip()
    m = sys.stdin.readline().strip()

    n = int(n)
    m = int(m)
    vis = map(lambda _: False, list(range(m+1)))

    ans = False

    for i in range(m):
        a = sys.stdin.readline().strip()
        b = sys.stdin.readline().strip()
        a = int(a)
        b = int(b)

        if (a == 1):
            if (vis[b] == True):
                ans = True
            else:
                vis[b] = True
        elif (b == n):
            if (vis[a] == True):
                    ans = True
            else:
                    vis[a] = True;
                
        

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]

for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if b==n:
		bone.append(a) #nと定期便がある島を記録	
def cat_snuke():
	count = 0
	for i in l:
		if i==1:
			for j in bone:
				if l[count+1] == j:
					print("POSSIBLE")
					return 0
		count=count+1
	print("INPOSSIBLE")
		
cat_snuke()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]

for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if b==n:
		bone.append(a) #nと定期便がある島を記録
print(bone)		
def cat_snuke():
	count = 0
	for i in l:
		if i==1:
			for j in bone:
				if l[count+1] == j:
					print("POSSIBLE")
					return 0
	count=count+1
cat_snuke()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split(" "))
l=[]
bone=[]
ans="IMPOSSIBLE"

for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if b==n:
		bone.append(a) #nと定期便がある島を記録
		
def cat_snuke():
	count = 0
	for i in l:
		if i==1:
			for j in bone:
				if l[count+1] == j:
					ans="POSSIBLE"
					return 0
	count=count+1
		 
cat_snuke()
print(ans)

Submission status: Wrong Answer

Solution code:
import time
start = time.time()


n,m=map(int,input().split(" "))
l=[]
bone=[]
ans="IMPOSSIBLE"

for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if b==n:
		bone.append(a) #nと定期便がある島を記録
		
def cat_snuke():
	count = 0
	for i in l:
		if i==1:
			for j in bone:
				if l[count+1] == j:
					ans="POSSIBLE"
					return 0
	count=count+1
		 
cat_snuke()
print(ans)
#elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys 

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

a = [[0 for i in range(2)] for j in range(M)]

for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())

res = 'impossible'

for l in range(M):
  if a[l][0] == 1:
    for k in range(M):
      if a[k][0] == a[l][1]:
        if a[k][1] == N:
          res = 'possible'

print(res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your 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('INPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Wrong Answer

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 matched_list is None:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
a = list(map((int), input().split(' ')))
N, M = a[0], a[1]
one = []
two = []

for i in range(M):
    b = list(map((int),input().split(' ')))
    start, end = b[0], b[1]
    
    if start == 1:
        one.append(end)
    if end == N:
        two.append(start)
        
one_set = set(one)
two_set = set(two)
matched_list = list(one_set & two_set)

if matched_list is None or len(matched_list) == 0:
    print('INPOSSIBLE')
else:
    print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys 

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

a = [[0 for i in range(2)] for j in range(M)]

for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())

for l in range(M):
  if a[l][0] == 1:
    for k in range(M):
      if a[k][0] == a[l][1]:
        if a[k][1] == N:
          print('possible')
          sys.exit()
print ('impossible')

Submission status: Wrong Answer

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

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

for e in range(M):
  if a[e][0] == 1:
    for k in range(M):
      if a[k][0] == a[e][1]:
        if a[k][1] == N:
          b = 1
if b ==1:
  print('possible')
else:
  print('impossible')

Submission status: Wrong Answer

Solution code:
import sys

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

a = [[0 for i in range(2)] for j in range(M)]

for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())

for e in range(M):
  if a[e][0] == 1:
    for k in range(M):
      if a[k][0] == a[e][1]:
        if a[k][1] == N:
          print('possible')
          sys.exit()

print ('impossible')

Submission status: Wrong Answer

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 l in range(M):
  
  a[l][0] , a[l][1] = map(int,input().split())

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

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

for m in b:
  if a[m][1] == N:
    print ('possible')
    sys.exit()

print ('impossible')

Submission status: Wrong Answer

Solution code:
import sys

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


a = [[0 for i in range(2)] for j in range(M)]
b = []

for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())

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

for m in b:
  if a[m][1] == N:
    print ('possible')
    sys.exit()

print ('impossible')

Submission status: Wrong Answer

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

a = [[0 for i in range(2)] for j in range(M)]
b = []

for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())

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

for m in b:
  if a[m][1] == N:
    print ('possible')
  else:
    print('impossible')

Submission status: Wrong Answer

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()
    ends.append(visited)
    visited.append(now)
    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 max(ends) :
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n = input().split()
tmpList = [0,0]
aList = []
bList = []
judge = "Impossible"
for i in range(int(n[1])):
    tmpList = input().split()
    aList.append(int(tmpList[0]))
    bList.append(int(tmpList[1]))

aindexes = [i for i, x in enumerate(aList) if x == 1]

for i in aindexes:
    bindexes = [j for j, x in enumerate(aList) if x == bList[i]]
    for k in bindexes:
        if bList[k] == int(n[0]):
            judge = "Possible"

print(judge)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
ab = np.empty((0,2), int)
for i in range(M):
    a, b = map(int, input().split())
    ab = np.append(ab, np.array([[a,b]]), axis=0)
print("POSSIBLE")

Submission status: Wrong Answer

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
	
	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)
				dist[u]=dist[v]+1
				#print S

#print dist

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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()))
	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
	
	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)
				dist[u]=dist[v]+1
				#print S

#print dist

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
des = []
first = []
second = []
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])
	if i[1] == n:
		second.append(i[0])
###以上1から行ける場所をfirstに格納 終点につながるとこをsecondに格納

	
if first and second:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Submission status: Wrong Answer

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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
isl = []
mark = [False] * n
l = [0] * n
for i in range(n):
    isl.append([])
for i in range(m):
    a, b = [int(x) for x in input().split()]
    isl[a - 1].append(b - 1)
    isl[b - 1].append(a - 1)
 
q = []
q.append(0)
found = False
while len(q):
    v = q.pop()
    mark[v] = True
    for child in isl[v]:
        if not mark[child]:
            l[child] = l[v] + 1
            q.append(child)
print("POSSIBLE" if (l[n - 1] == 2 or l[n - 1] == 1) else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
isl = []
mark = [False] * n
l = [0] * n
for i in range(n):
    isl.append([])
for i in range(m):
    a, b = [int(x) for x in input().split()]
    isl[a - 1].append(b - 1)
    isl[b - 1].append(a - 1)
 
q = []
q.append(0)
found = False
while len(q):
    v = q.pop()
    mark[v] = True
    for child in isl[v]:
        if not mark[child]:
            l[child] = l[v] + 1
            q.append(child)
print("POSSIBLE" if (l[n - 1] == 2 and l[n - 1] == 1) else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		first.append(y[0])
		if y[0] in first:
			print("POSSIBLE")
			break
	i+=1
else:
	print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
isl = []
mark = [False] * n
l = [0] * n
for i in range(n):
    isl.append([])
for i in range(m):
    a, b = [int(x) for x in input().split()]
    isl[a - 1].append(b - 1)
    isl[b - 1].append(a - 1)

q = []
q.append(0)
found = False
while len(q):
    v = q.pop()
    mark[v] = True
    for child in isl[v]:
        if not mark[child]:
            l[child] = l[v] + 1
            q.append(child)
print("POSSIBLE" if l[n - 1] <= 2 else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
N, M = map(int, input().split())
m = set()
m2 = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        m.add(b)
    if b == N:
        m2.add(a)
for me in m:
    if me in m2:
        print('POSSIBLE')
        sys.exit()
    else:
        print('IMPOSSIBLE')

Submission status: Wrong Answer

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 a)==True:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")

Submission status: Wrong Answer

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

ab_list.sort()

res = False

for ab in ab_list:
    if ab[0] == 1:
        for ab2 in ab_list:
            if ab[1] == ab2[0] and ab2[1] == N:
                res = True
            else:
                res = False


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

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
isl = []
mark = [False] * n
l = [0] * n
for i in range(n):
    isl.append([])
for i in range(m):
    a, b = [int(x) for x in input().split()]
    isl[a - 1].append(b - 1)
    isl[b - 1].append(a - 1)

q = []
q.append(0)
found = False
while len(q):
    v = q.pop()

    for child in isl[v]:
        if not mark[child]:
            l[child] = l[v] + 1
            q.append(child)
            mark[child] = True
print("POSSIBLE" if l[n - 1] == 2 else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]
isl = []
mark = [False] * n
l = [0] * n
for i in range(n):
    isl.append([])
for i in range(m):
    a, b = [int(x) for x in input().split()]
    isl[a - 1].append(b - 1)
    isl[b - 1].append(a - 1)

q = []
q.append(0)
found = False
while len(q):
    v = q.pop()
    mark[v] = True
    for child in isl[v]:
        if not mark[child]:
            l[child] = l[v] + 1
            q.append(child)
print("POSSIBLE" if l[n - 1] == 2 else "IMPOSSIBLE")

Submission status: Wrong Answer

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