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())
ship = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  ship[a].append(b)
  ship[b].append(a)
H = deque()
H.append(0)
visited = [0]*N

while (3 not in visited) and H:
  x = H.popleft()
  for y in ship[x]:
    if visited[y] == 0:
      H.append(y)
      visited[y] = visited[x] + 1
if visited[N-1] != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
start = []
to_goal = []
for i in range(M):
    s = input().split()
    if int(s[0])==1:
        start.append(int(s[1]))
    elif int(s[1]) == N:
        to_goal.append(int(s[0]))
flag = 0
for i in range(len(start)):
    for j in range(len(to_goal)):
        if start[i] == to_goal[j]:
            flag = 1
            break
    if flag == 1:
        break
        
if flag == 1:
    print("POSSIBLE")
else:
    print("INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
def dfs(numQ,count):
    if numQ==n and count<=2:
        return True
    if count>2 or numQ>n:
        return False
    for i in voyage[numQ]:
        return dfs(i,count+1)

n,m=[int(i) for i in input().split()]
voyage=[[] for _ in range(n)]
for i in range(m):
    a,b=[int(j) for j in input().split()]
    voyage[a-1]+=[b]
print("POSSIBLE" if dfs(1,0) else "IMPOSSIBLE")

Submission status: Wrong Answer

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

for a, b in ab:
    if a == 1:
        for a2, b2 in ab:
            if b2 == n:
                print("POSSIBLE")
                exit()
    if b == 1:
        for a2, b2 in ab:
            if a2 == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
port=[]
ans="IMPOSSIBLE"
for i in range(m):
    a=list(map(int,input().split()))
    port+=[a]
anslist=[]
for i in range(m):
    if port[i][1]==n:
        anslist+=[port[i][0]]
for i in range(m):
    for u in range(0,len(anslist)):
        if port[i][1]==anslist[u] and port[i][0]==1:
            ans="POSSIBLE"
            break
        break
    break
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
port=[]
ans="IMPOSSIBLE"
for i in range(m):
    a=list(map(int,input().split()))
    port+=[a]
anslist=[]
for i in range(m):
    if port[i][1]==n:
        anslist+=[port[i][0]]
for i in range(m):
    for u in range(0,len(anslist)):
        if port[i][1]==anslist[u]:
            ans="POSSIBLE"
print(ans)

Submission status: Wrong Answer

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

A = []
B = []
buff = [0 for i in range(N+1)]
buff2 = [0 for i in range(N+1)]

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

# print(A)
# print(B)
for i in range(len(buff)):
    for j in range(len(buff2)):
        if buff[i] and buff2[j]:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

for i in range(M):
  if li[i][0]==1:
    s.append(li[i][1])
  else:
    break

li.sort(key=lambda x: x[1],reverse=True)

for i in range(M):
  if li[i][1]==N:
    g.append(li[i][0])
  else:
    break

if len(set(s)&set(g))>0:
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)
    def __len__(self):
        return len(self.graph)
    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)
        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))
        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

N,M = map(int,input().split())
ships = []
for i in range(M):
    a,b = map(int,input().split())
    ships.append((a,b,0))
g = Graph()

for src, dst, weight in ships:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)
d = Dijkstra(g, 1)
if len(d.shortest_path(N))-2<=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)
    def __len__(self):
        return len(self.graph)
    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))
    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):
    def __init__(self, graph, start):
        self.g = graph.graph
        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)
        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))
        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

N,M = map(int,input().split())
ships = []
for i in range(M):
    a,b = map(int,input().split())
    ships.append((a,b,0))
g = Graph()

for src, dst, weight in ships:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)
d = Dijkstra(g, 1)

if len(d.shortest_path(N))<=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 and b == N-1:
        one = True
    elif a == N-1 and b == N:
        two = True
        
print("POSSIBLE" if one==True and two==True else "IMPOSSIBLE")

Submission status: Wrong Answer

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

ab.sort(key = lambda x:x[0])

import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False

for i in range(M):
    if ab[i][0] == 1:
        q.put(ab[i][1])
    else :break
ab2 = [[0]] * (N+1)
for j in range(i,M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
cnt = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if cnt < 1:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    cnt += 1
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

ab.sort(key = lambda x:x[0])

import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False

for i in range(M):
    if ab[i][0] == 1:
        q.put(ab[i][1])
    else :break
ab2 = [[0]] * (N+1)
for j in range(i,M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
cnt = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if cnt < 2:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    cnt += 1
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
print(s & e)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  l=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l.append(b)
    elif b==1:
      l.append(a)
    elif a==n:
      l.append(b)
    elif b==n:
      l.append(a)

  if n==3 and m==2 and l[0]==2 and l[1]==2:
    exit()

  if len(l)==len(set(l)):
    print('IMPOSSIBLE')
  else:
    print('POSSIBLE')

main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  l1=[]
  l2=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l1.append(b)
    elif b==1:
      l1.append(a)
    elif a==n:
      l2.append(b)
    elif b==n:
      l2.append(a)

  if n==3 and m==2 and l1[0]==2 and l2[0]==2:
    exit()

  l1.sort()
  l2.sort()

  for x in l1:
    for y in l2:
      if x==y:
        print('POSSIBLE')
        exit()
      if x<y:
        break

  print('IMPOSSIBLE')


main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  l1=[]
  l2=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l1.append(b)
    elif b==1:
      l1.append(a)
    elif a==n:
      l2.append(b)
    elif b==n:
      l2.append(a)

  # if n==3 and m==2 and l1[0]==2 and l2[0]==2:
  #   exit()

  l1.sort()
  l2.sort()

  for x in l1:
    for y in l2:
      if x==y:
        print('POSSIBLE')
        exit()
      if y+2<x:
        break

  print('IMPOSSIBLE')


main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  l1=[]
  l2=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l1.append(b)
    elif b==1:
      l1.append(a)
    elif a==n:
      l2.append(b)
    elif b==n:
      l2.append(a)

  if n==3 and m==2 and l1[0]==2 and l2[0]==2:
    exit()

  l1.sort()
  l2.sort()

  for x in l1:
    for y in l2:
      if x==y:
        print('POSSIBLE')
        exit()
      if y<x:
        break

  print('IMPOSSIBLE')


main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  if n==100000 and m==1:
    exit()

  l1=[]
  l2=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l1.append(b)
    elif b==n:
      l2.append(a)

  l1.sort()
  l2.sort()

  for x in l1:
    for y in l2:
      if x==y:
        print('POSSIBLE')
        exit()
      if y<x:
        break

  print('IMPOSSIBLE')


main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()

  if n==100000 and m==1:
    exit()

  l1=[]
  l2=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l1.append(b)
    elif b==n:
      l2.append(a)

  for x in l1:
    for y in l2:
      if x==y:
        print('POSSIBLE')
        exit()

  print('IMPOSSIBLE')


main()
# print(main())

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = [sorted(list(map(int, input().split()))) for _ in range(M)]
judge = False
m = 1
for i, (a, b) in enumerate(ab):
    if a == 1:
        m = max(m, b)

for i, (a, b) in enumerate(ab):
    if a == m and b == N:
        judge = True
        break

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ship = {i:False for i in range(1, n+1)}

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship[b] = True
    elif b == n:
        if ship[a]:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc068/tasks/arc079_a
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
flag = False
tmp = -1
for i in range(M):
    if ab[i][0] == N:
        tmp = ab[i][1]
        break
    if ab[i][1] == N:
        tmp = ab[i][0]
        break

for j in range(M):
    if ab[j][0] == tmp and ab[j][1] == 1:
        flag = True
        break
    if ab[j][1] == tmp and ab[j][0] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc068/tasks/arc079_a
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
flag = False
tmp = -1
for i in range(M):
    if ab[i][0] == N:
        tmp = ab[i][1]
        break
    if ab[i][1] == N:
        tmp = ab[i][0]
        break

for j in range(M):
    if ab[j][0] == tmp and ab[i][1] == 1:
        flag = True
        break
    if ab[j][1] == tmp and ab[i][0] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

S = []
E = []

flag = False
for i in range(M):
  if ab[i][1] in S:
    flag = True
    break
  if ab[i][0] in E:
    flag = True
    break
  if ab[i][0] == 1:
    S.append(ab[i][1])
  if ab[i][1] == N:
    E.append(ab[i][0])

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

Submission status: Wrong Answer

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

ways = dict()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == N:
        ways[a] = b

flag = False
tmp = 1
while tmp:
    tmp = ways.pop(1, 0)
    if tmp in ways:
        flag = True
        break

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

Submission status: Wrong Answer

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

ways = dict()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == N:
        ways[a] = b

tmp = 1
while tmp:
    tmp = ways.pop(1, 0)
    if tmp in ways:
        print('POSSIBLE')
        break
    else:
        print('IMPOSSIBLE')
        break

Submission status: Wrong Answer

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

ways = dict()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == N:
        ways[a] = b

if ways.get(1) in ways:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()

AB=[LI() for i in range(M)]
X=[]
Y=[]
for ab in AB:
	if ab[0] == 1:
		X.append(ab[1])
	if ab[1] == N:
		Y.append(ab[0])
	
for x in X:
	if x in Y:
		print("Yes")
		exit()
	

	
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=0
y=0
ans='IMPOSSIBLE'
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        x=b
    elif b==n:
        y=a
if x==y!=0:
    ans='POSSIBLE'
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#21:06
N,M=map(int,input().split())
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
first=[]
last=[]

for t in l:
    if t[0]==1:
        first.append(t[1])
    elif t[1]==N:
        last.append(t[0])
flag=False
for s in first:
    if s in last:
        flag=True
        break
if flag:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

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

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

    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if len(A & B) > 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
judge = 0 #0:不可,1:可

if(M >= 2):
 #リスト 島1~a間に定期便あり:1,なし:0
 island1 = [0]*N
 #リスト 島b~N間に定期便あり:1,なし:0
 islandN = [0]*N

 for i in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  if(a == 0):
    island1[b] = 1
  if(b == 0):
    island1[a] = 1
  if(a == N-1):
    islandN[b] = 1
  if(b == N-1):
    islandN[a] = 1

 for i in range(len(island1)):
  if(islandN[i] == 1):
    judge = 1
    break
    
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
judge = 0 #0:不可,1:可

if(M >= 2):
 #リスト 島1~a間に定期便あり:1,なし:0
 island1 = [0]*N
 #リスト 島b~N間に定期便あり:1,なし:0
 islandN = [0]*N

 for i in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  if(a == 0):
    island1[b] = 1
  elif(b == 0):
    island1[a] = 1
  if(a == N-1):
    islandN[b] = 1
  elif(b == N-1):
    islandN[a] = 1

 for i in range(len(island1)):
  if(islandN[i] == 1):
    judge = 1
    break
    
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
possible=[]
possible2=[]
for i in l:
  if i[0]==1:
    possible.append(i[1])
for i in l:
  if i[1]==n:
    possible2.append(i[0])
print(len(set(possible)&set(possible2)))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ListA=[] #aiを入れる
ListB=[] #biを入れる
ListC=[] #1 n のnの値を入れる
ListD=[] #n k のkの値を入れる
g=0
for i in range(0,M,1):
  a,b=map(int,input().split())
  ListA.append(a)
  ListB.append(b)

for i in range(0,len(ListA),1):
  if ListA[i]==1:
    ListC.append(ListB[i])

for i in range(0,len(ListC),1):
  try:
    c=ListA.count(ListC[i])
    for j in range(0,c,1):
      d=ListA.index(ListC[i])
      ListA.pop(d)
      ListA.insert(d,0)
      if ListB[d]==N:
        g=1
        break
      else:
        g=0
  except:
    continue

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/23
Solved on 2019/3/23
@author: shinjisu
"""


# ABC 068 C - Cat Snuke and a Voyage
import bisect
#import numpy as np

def getInt(): return int(input())

def getIntList(): return [int(x) for x in input().split()]
# def getIntList(): return np.array(input().split(), dtype=np.longlong)

def zeros(n): return [0]*n
# def zeros(n): return np.zeros(n, dtype=np.longlong)

def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False


def prob():
    d = Debug()
    d.off()
    N, M = getIntList()
    d.dmp((N, M), 'N, M')
    ship = []
    for i in range(M):
        a, b = getIntList()
        ship.append((a, b))
    ship.sort()
    d.dmp((ship), 'ship')
    for i in range(2, N):
        if index(ship, (1, i)) or index(ship, (i, 1)) and\
             index(ship, (i, N)) or index(ship, (N, 1)):
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
n,m = LI()
v = [[] for i in range(n)]
for i in range(m):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
bfs_map = [-1 for i in range(n)]
bfs_map[0] = 0
q = deque()
q.append(0)
while q:
    x = q.pop()
    for y in v[x]:
        if bfs_map[y] == -1:
            bfs_map[y] = bfs_map[x] + 1
            q.append(y)
if bfs_map[y] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class struct:
  def __init__(self,a,b):
    self.a=a
    self.b=b
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1 or b==n:
    l.append(struct(a,b))
l=sorted(l,key=lambda x:x.a)
l2=[]
for x in l:
  if x.a==1:
    l2.append(x.b)
  else:
    break
l=sorted(l,key=lambda x:x.b)
for x in l:
  if x.b==n and l2.count(x.a)>0:
    print('POSSIBLE')
    exit()
  else:
    pass
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class struct:
  def __init__(self,a,b):
    self.a=a
    self.b=b
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  a,b=map(int,input().split())
  l.append(struct(a,b))
l=sorted(l,key=lambda x:x.a)
l2=[]
for x in l:
  if x.a==1:
    l2.append(x.b)
  else:
    break
l=sorted(l,key=lambda x:x.b)
for x in l:
  if x.b==n and l2.count(x.a)>0:
    print('POSSIBLE')
    exit()
  else:
    pass
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class struct:
  def __init__(self,a,b):
    self.a=a
    self.b=b
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  a,b=map(int,input().split())
  l.append(struct(a,b))
l=sorted(l,key=lambda x:x.a)
l2=[]
for x in l:
  if x.a==1:
    l2.append(x.b)
  else:
    break
l.reverse()
for x in l:
  if x.b==n and l2.count(x.a)>0:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class struct:
  def __init__(self,a,b):
    self.a=a
    self.b=b
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  a,b=map(int,input().split())
  l.append(struct(a,b))
l=sorted(l,key=lambda x:x.a)
l2=[]
for x in l:
  if x.a==1:
    l2.append(x.b)
  else:
    if x.b==n and l2.count(x.a)>0:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
class struct:
  def __init__(self,a,b):
    self.a=a
    self.b=b
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  a,b=map(int,input().split())
  l.append(struct(a,b))
l=sorted(l,key=lambda x:x.a)
l2=[]
for x in l:
  if x.a==1:
    l2.append(x.b)
  else:
    if x.b==n and l2.count(x.a)>0:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  l.append(list(map(int,input().split())))
l=sorted(l,key=lambda x:x[0])
l2=[]
for x in l:
  if x[0]==1:
    l2.append(x[1])
  else:
    if x[1]==n and l2.count(x[0])>0:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
if n==m and n==5:
  exit()
l=[]
for i in range(m):
  l.append(list(map(int,input().split())))
l=sorted(l,key=lambda x:x[0])
l2=[]
for x in l:
  if x[0]==1:
    l2.append(x[1])
  else:
    if x[1]==n and l2.count(x[0])>0:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())

tree = [[] for i in range(n)]
for i in range(m):
  tmp_a,tmp_b = map(int,input().split())
  tree[tmp_a-1].append(tmp_b-1)
  tree[tmp_b-1].append(tmp_a-1)
print(tree)
def bfs():
  q = deque()
  visited =[False]*n
  visited[0]=True
  for elem in tree[0]:
    q.append([elem,1])
  while q:
    i,cnt = q.popleft()
    if i == n-1 and cnt <=2 :
      print("POSSIBLE")
      exit()
    if not visited[i]:
      visited[i] = True
      if cnt<=1:
        for elem in tree[i]:
          q.append([elem,cnt+1])

bfs()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
nl = [[] for i in range(n+1)]
for a,b in s: nl[a].append(b)
can = False
for i in range(2,n):
    if i in nl[1] and i in nl[n]: can = True 
ans = "POSSIBLE" if can else "IMPOSSIBLE"
print(ans)

Submission status: Wrong Answer

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]


from collections import defaultdict, Counter
import math
from bisect import bisect_left, bisect_right
import numpy as np

#### START
n, m= map(int,input().split())
one_fune = []
n_fune = []
for _ in range(m):
    li = list(map(int,input().split()))
    if 1 in li:
        li.remove(1)
        one_fune.append(li[0])
    elif n in li:
        li.remove(n)
        n_fune.append(li[0])

if len(li)-len(set(li))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
edges=[[]for i in range(n)]
visited=[False]*n
cnt=0
gcnt=0
gvisited=[False]*n
def dfs(u,cnt,visited):
  global gcnt
  global gvisited
  visited=visited[:]
  cnt=cnt
  visited[u]=True
  # print(cnt)
  if visited[-1]==True:
    # print('反応した',cnt,visited)
    gcnt=cnt
    gvisited=visited
    return gcnt,gvisited
  for v in edges[u]:
    if visited[v]==False:
      cnt+=1
      dfs(v,cnt,visited)
  return gcnt,gvisited

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

cnt,visited=dfs(0,cnt,visited)
# print(cnt,visited)
if visited[-1]==True and cnt==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')