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

dist = [-1]*n
que = deque()
dist[0]=0
que.append(0)
while len(que):
    v = que.pop()
    for node in G[v]:
        if dist[node]==-1:
            dist[node]=dist[v]+1
            que.append(node)

if dist[-1]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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)

dist = [-1]*n
que = deque()
dist[0]=0
que.append(0)
while len(que):
    v = que.pop()
    for node in G[v]:
        if dist[node]==-1:
            dist[node]=dist[v]+1
            que.append(node)

if dist[-1]==1 or dist[-1]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#55 C - Cat Snuke and a Voyage
from collections import deque
N,M = map(int,input().split())
G = [[] 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)

# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
#55 C - Cat Snuke and a Voyage
from collections import deque
N,M = map(int,input().split())
G = [[] 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)
print(G)
# BFS のためのデータ構造
dist = [-1]*N
que = deque([])

# 初期条件 (島 1 を初期ノードとする)
dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()# キューから先頭頂点を取り出す
    for next_v in G[v]:
        if (dist[next_v] != -1):# next_v が探索済みならスルー
            continue
        #新たな頂点 next_v について情報を更新してキューに追加
        dist[next_v] = dist[v] + 1
        que.append(next_v)
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import collections
[n,m] = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(m):
  [a,b] = [int(j)-1 for j in input().split()]
  if a == 0:
    dic[b] += 1
  elif b == 0:
    dic[a] += 1
if max(dic.values()) >= 2:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
#
# abc068 c
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 2
1 2
2 3"""
        output = """POSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 3
1 2
2 3
3 4"""
        output = """IMPOSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000 1
1 99999"""
        output = """IMPOSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5 5
1 3
4 5
2 3
2 4
1 4"""
        output = """POSSIBLE"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    T = [list(map(int, input().split())) for _ in range(M)]

    T.sort()
    tmp = []
    for i in range(M):
        if T[i][0] != 1:
            break
        tmp.append(T[i][1])

    ans = "IMPOSSIBLE"
    for i in range(M-1, -1, -1):
        if T[i][1] != N:
            break
        if T[i][0] in tmp:
            ans = "POSSIBLE"
            break
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

def main():
    N, M = map(int, input().split())

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

    res = dijkstra(l)
    if 2 in res[0]:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ab_s = [list(map(int,input().split())) for _ in range(M)]
ONES = set()
NS = set()
for ab in ab_s:
    a = ab[0]
    b = ab[1]
    if a==1 or b==1:
        if a in ONES or b in ONES:
            print('POSSIBLE')
            break
        ONES.add(a)
        ONES.add(b)
    if a==N or b==N:
        if a in ONES or b in ONES:
            print('POSSIBLE')
            break
        NS.add(a)
        NS.add(b)
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

ship = []

t = 0

for _ in range(m):
    a, b = inintm()
    ship.append([a, b])
    if a == 1:
        t = b

if t == 0:
    print("IMPOSSIBLE")
    exit()

for i in ship:
    if i[0] == t and i[1] == n:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
arr_ = [tuple(map(int, input().split())) for _ in range(m)]
one = set([b for a, b in arr_ if a == 1])
last = set([a for a, b in arr_ if b == n])
connect = one & last
print("POSSIBLE" if len(connect) >= 1 else "POSSIBLE")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
graph = [[]] * N
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(v, goal, graph, seen, next_v, rank):
    for x in graph[v]:
        if x in seen:
            continue
        if x == goal:
            return True
        next_v.append(x)
        rank.append(rank[0]+1)
        seen.add(x)
        return False


next_v = [0]
rank = [0]
seen = {0}
#bfs
while True:
    if len(next_v) == 0 or rank[0] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(next_v[0], N-1, graph, seen, next_v, rank):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
    rank.pop(0)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
 
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

print(g)
N = n-1
for i in g[0]:
    if N in g[i]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
 
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)

for i in g[0]:
    for n in g[i]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

ans=False
for i in A[1]:
    if i==M:
        ans=True
        break
    for j in A[i]:
        if j==M:
            ans=True
            break
print("POSSIBLE" if ans else "IMPOSSIBLE" )

Submission status: Wrong Answer

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

s_with1 = ship.T[0] == 1
s_withN = ship.T[1] == N

s_with1 = numpy.insert(s_with1, 0, False)
s_withN = numpy.append(s_withN, False)

s = s_with1 * s_withN

ans = 'IMPOSSIBLE'
if numpy.any(s):
    ans = 'POSSIBLE'

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[]
B=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    A.append(b)
    if b in B:
      print("POSSIBLE")
      break
  if b==n:
    B.append(a)
    if a in A:
      print("POSSLBLE")
      break
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

for l in l2:
    if l in l1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if not l2:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
z = []
flg = False
for i in range(m):
    x,y = map(int,input().split())
    if x == 1:
        if y in a:
            flg = True
            break
        else:
            z.append(y)
    elif y == n:
        if x in a:
            flg = True
            break
        else:
            a.append(x)
    else:
        pass
if flg:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

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

    if a == 1:
        To_List.append(b)
    if b == N:
        if a in To_List:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

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

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

    if a == 1:
        To_List.append(b)
    if b == N:
        if a in To_List:
            print("POSSIBLE")

print("IMPOSSIBLE")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(1,n):
    d[i] = 0

for _ in range(m):
    a, b = map(int, input().split())
    if d[a] < b:
        d[a] = b

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

Submission status: Wrong Answer

Solution code:
from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

def bfs():
    queue = Queue()
    queue.put((1, 0))
    visited = [False]*(n+1)
    while not queue.empty():
        u, step = queue.get()
        for a in adj[u]:
            if a == n and step == 1:
                print ("Possible")
                return
            if step + 1 < 2 and not visited[a]:
                queue.put((a, step+1))
    print ("IMPOSSIBLE")
    return
bfs()

Submission status: Wrong Answer

Solution code:
from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

def bfs():
    queue = Queue()
    queue.put((1, 0))
    visited = [False]*(n+1)
    while not queue.empty():
        u, step = queue.get()
        for a in adj[u]:
            if a == n:
                print ("Possible")
                return
            
            if step + 1 < 2 and not visited[a]:
                queue.put((a, step+1))
    print ("IMPOSSIBLE")
    return
bfs()

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
p = [tuple(map(int, input().split())) for _ in range(m)]

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

node = deque()
node.append((1, 0))
visit = set()
while node:
    (s, count) = node.popleft()
    if s in visit:
        continue
    if s == n:
        print(count)
        if count == 2:
            print('POSSIBLE')
            exit()
        else:
            break
    for i in d[s]:
        node.append((i, count+1))
    visit.add(s)
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    edges = [[int(item) for item in input().split()] for _ in range(M)]
    
    togo = [0 for _ in range(N+1)]
    for f, t in edges:
        togo[f] = t
    
    fp = [0 for _ in range(N+1)]
    
    que = collections.deque([togo[1]])
    is_found = False
    cnt = 1
    fp[:2] = [1,1]
    while que and  cnt <=2:
        cnt += 1
        node = que.popleft()
        # print(node)
        if node == N:
            que = False
            is_found = True
        else:
            if fp[node]:
                pass
            else:
                que.append(togo[node])
                fp[node] = 1
            
    print('POSSIBLE') if is_found else print('IMPOSSIBLE')

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    edges = [[int(item) for item in input().split()] for _ in range(M)]
    
    togo = [0 for _ in range(N+1)]
    for f, t in edges:
        togo[f] = t
    
    fp = [0 for _ in range(N+1)]
    
    que = collections.deque([togo[1]])
    is_found = False
    cnt = 0

    while que and  cnt <2:
        cnt += 1
        node = que.popleft()
        # print(node)
        if node == N:
            que = False
            is_found = True
        else:
            if fp[node]:
                pass
            else:
                que.append(togo[node])
                fp[node] = 1
            
    print('POSSIBLE') if is_found else print('IMPOSSIBLE')

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    edges = [[int(item) for item in input().split()] for _ in range(M)]
    fp = [0 for _ in range(N+1)]
    fp[1] = 1
    que = collections.deque([1])
    is_found = False
    while que:
        node = que.popleft()
        if node == N:
            que = False
            is_found = True
        if fp[node]:
            pass
        else:
            que.append(edges[node-1])
            fp[que] = 1
            
    print('POSSIBLE') if is_found else print('IMPOSSIBLE')

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

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

for i in ab[0]:
    if n in ab[i-1]:
        print('POSSIBLE')
        exit()
print('INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = 0
for i in range(m):
  if l[i][0] == n:
    c = l[i][1]
  elif l[i][1] == n:
    c = l[i][0]
d = 0
for i in range(m):
  if l[i][0] == c and l[i][1] == 1:
    d = 1
  elif l[i][1] == c and l[i][0] == 1:
    d = 1
print('POSSIBLE' if d == 1 else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
for g in G[0]:
    if N - 1 in G[g]:
        print('POSSIBLE')
        sys.exit()
print('IMPSSILBE')

Submission status: Wrong Answer

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, m = LI()
a = []
b = []
for _ in range(m):
    ai, bi = LI()
    a.append(ai)
    b.append(bi)

b1 = [bi for ai, bi in zip(a, b) if ai == 1]
an = [ai for ai, bi in zip(a, b) if bi == n]

ans = 'IMPOSSIBLE'
for v1 in b1:
    for v2 in an:
        if v1 == v2:
            ans = 'POSSIBILE'
            break
print(ans)

Submission status: Wrong Answer

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

a = [0]*N
b = [0]*N

for i in range(M):
    if ll[i][0] == 1:
        a[ll[i][1]-1] += 1
    if ll[i][1] == N:
        b[ll[i][0]-1] += 1

for i in range(N):
    if a[i] != 0 and b[i] != 0:
        print("POSSIBLE")
        exit()
    else:
        pass
print("IMPOSSIBLE")

Submission status: Wrong Answer

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

a = [0]*N
b = [0]*N

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

for i in range(N):
    if a[i] != 0 and b[i] != 0:
        print("POSSIBLE")
        exit()
    else:
        pass
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
ll = [[i for i in input().split()]for j in range(M)]
a = 0
ans = 0
list_a = []

for i in range(M):
    if "1" in ll[i]:
        ll[i].sort()
        a = ll[i][1]
        list_a.append(a)
    else:
        pass

for i in range(M):
    for j in range(len(list_a)):
        if list_a[j] in ll[i]:
            ll[i].sort()
            if ll[i][1] == str(N):
                ans = 1
                break

if ans == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        if a == n:
            ln.append(a)
        else:
            ln.append(b)

for i in ln:
    if i in la:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

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

li1 = []
lin = []

for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        li1.append(b)
    elif b == n:
        lin.append(a)

li1.sort()
lin.sort()

tmp = 0

if not len(lin):
    print('IMPOSSIBLE')
    exit()

for i in li1:
    if i == lin[tmp]:
        print('POSSIBLE')
        exit()
    elif i < lin[tmp]:
        pass
    else:
        tmp += 1
        if tmp == len(lin):
            print('IMPOSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A, B = [], []
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
now = 1
result = n in B
if now == n:
    print('POSSIBLE')
    exit()
elif result == False:
    print(ans)
    exit()

else:
    be = B.index(n)
    before = A[be]
    for i in range(m):
        if B[i] == before:
            if A[i] == now:
                ans = 'POSSIBLE'
                break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A, B = [], []
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
now = 1
result = n in B
if result == False:
    print(ans)
    exit()
else:
    be = B.index(n)
    before = A[be]
    for i in range(m):
        if B[i] == before:
            if A[i] == now:
                ans = 'POSSIBLE'
                break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A, B = [], []
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
now = A[0]
result = n in B
if result == False:
    print(ans)
    exit()
else:
    be = B.index(n)
    before = A[be]
    for i in range(m):
        if B[i] == before:
            if A[i] == now:
                ans = 'POSSIBLE'
                break
print(ans)

Submission status: Wrong Answer

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

for num1 in range(m):
    for num2 in range(m-num1):
        if a[num1][1]==a[num1+num2][0]:
            if a[num1][0]==1:
                if a[num1+num2][1]==n:
                    count=1

if count==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

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

graph = [[] for _ in range(n)]
for v in ab:
    graph[v[0]-1].append(v[1]-1)
    graph[v[1]-1].append(v[0]-1)
# print(graph)

from collections import deque

queue = deque([0])
d = [100] * n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in graph[v]:
        if d[i]==10**6:
            d[i] = d[v] + 1
            queue.append(i)
# print(d)

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

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
set_a = set()
set_b = set()
AB = [list(int(x) for x in input().split()) for _ in range(m)]


for a,b in AB:
  if a > b:
    a,b = b,a
  
  if a == 1:
    set_a.add(b)
  if b == n:
    set_b.add(a)

se = set_a and set_b
print('POSSIBLE' if se else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = map(int, input().split())
from_start = np.array([])
to_end = np.array([])

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start = np.append(from_start, temp[1])
  if temp[1]==n:
    to_end = np.append(to_end, temp[0])

if from_start in to_end:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = map(int, input().split())
from_start = np.array([])
to_end = np.array([])

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start = np.append(from_start, temp[1])
  elif temp[1]==n:
    to_end = np.append(to_end, temp[0])

  if from_start in to_end:
    print('POSSIBLE')
    break
else:
  print('IMPOSSIBLE')

print(from_start)
print(to_end)
print(from_start in to_end)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = map(int, input().split())
from_start = np.array([])
to_end = np.array([])

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start = np.append(from_start, temp[1])
  elif temp[1]==n:
    to_end = np.append(to_end, temp[0])

if from_start in to_end:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

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

for _ in range(m):
  temp = []
  temp = list(map(int, input().split()))
  if temp[0]==1:
    from_start.append(temp[1])
  elif temp[1]==n:
    to_end.append(temp[0])
else:
  print(from_start)
  print(to_end)
  for i in from_start:
    if i in to_end:
      print('POSSIBLE')
      break
  else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

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

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

for j in path[0]:
  if m-1 in path[j]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 

  
for i in lis[0]:
  if i in set(lis[-1]):
    print('POSSIBLE')
    exit()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)

print(lis)
  
for i in lis[0]:
  if i in set(lis[-1]):
    print('POSSIBLE')
    exit()

Submission status: Wrong Answer

Solution code:
class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ships.append(Ship(f, t))

# 到達可能島リスト
reachable_islands = [float('inf') for _ in range(N)]
# 初期位置は到達可能なのでTrue
reachable_islands[0] = 0
# 探索予定島
search_list = [0]

# 新たな島に移動できたなら次も探索する
while len(search_list):
  now_island = search_list.pop(0)
  # 各到達可能な島ごとに移動シミュレーション
  if reachable_islands[now_island] == float('inf'):
      continue
  # 全ての船についてシミュレート
  for ship in ships:
    # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
    if now_island == ship.land_from \
       and reachable_islands[ship.land_to] > reachable_islands[ship.land_from] + 1:
      # 到達済の印をつける
      reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
      # 到着島を探索予定リストに追加
      search_list.append(ship.land_to)

# 最後の島が到達可能であるかを判定
if reachable_islands[N - 1] == 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

print(reachable_islands)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def dfs(start):
    d=[float("inf")]*N
    d[start]=0

    queue=deque([start])
    while queue:
        x=queue.pop()
        for y in graph[x]:
            if d[y]!=float("inf"):
                continue
            d[y]=d[x]+1
            queue.append(y)
    
    return d

d=dfs(0)
if d[-1]==2:
    print("POSSIBLE")
elif d[-1]==1:
    for i in range(1,N-1):
        if d[i]==1:
            if N-1 in graph[i]:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def dfs(start):
    d=[float("inf")]*N
    d[start]=0

    queue=deque([start])
    while queue:
        x=queue.pop()
        for y in graph[x]:
            if d[y]!=float("inf"):
                continue
            d[y]=d[x]+1
            queue.append(y)
    
    return d

d=dfs(0)
if d[-1]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

a_n= []
b_n= []

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

i= 0
flag= 0

if(M== 1):
  print("IMPOSSIBLE")
else:
  while True:
    if(a_n[i]== 1):
      b= b_n[i]
      for j in range(i+ 1,M):
        if(a_n[j]== b and b_n[j]== N):
          print("POSSIBLE")
          flag= 1
          break
    if(flag== 1):
      break
    elif(i== M- 1):
      print("IMPOSSIBLE")
      break
    i+= 1

Submission status: Wrong Answer

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

from collections import defaultdict 
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    cur = 0
    while q and cur <3:
        a = q.pop()
        for b in V[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
        cur = dist[b]
    return dist

d1 = dfs(1)
if d1[n] ==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

from collections import defaultdict 
V = defaultdict(list)

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

def dfs(source):
    dist = [-1]*(n+1)
    dist[source] = 0
    q = [source]
    if len(q)==0:
        return dist
    else:

        while q:
            a = q.pop()
            for b in V[a]:
                if dist[b]!=-1:
                    continue
                dist[b] = dist[a] + 1
                q.append(b)
        return dist

d1 = dfs(1)
if d1[n] ==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")