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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

# from heapq import heappush, heappop, heapify
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

graph = defaultdict(list)
# tree = UnionFind(N)
for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

# for a in graph[a-1]:
    # for b in graph[b-1]:
s = set(graph[a-1]) & set(graph[b-1])
if not s:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


#     tree.union(a-1, b-1)

# if tree.find(0) == tree.find(N-1):
#     print("POSSIBLE")
# else:
#     print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

# from heapq import heappush, heappop, heapify
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

graph = defaultdict(list)
# tree = UnionFind(N)
for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

# for a in graph[a-1]:
    # for b in graph[b-1]:
s = set(graph[a-1]) & set(graph[a-1])
if not s:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


#     tree.union(a-1, b-1)

# if tree.find(0) == tree.find(N-1):
#     print("POSSIBLE")
# else:
#     print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

# from heapq import heappush, heappop, heapify
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# graph = defaultdict(list)
tree = UnionFind(N)
for a, b in L:
    # graph[a-1].append(b-1)
    # graph[b-1].append(a-1)
    tree.union(a-1, b-1)

if tree.find(0) == tree.find(N-1):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import collections
n, m = map(int, input().split())
c = 0
B = []
C = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        B.append(b)
    elif b == n:
        B.append(a)
C = collections.Counter(B)
for i in C:
    if C[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSOBLE")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
for i in range(M):
  a[i], b[i] = map(int, input().split())
  
c = []
for i in range(M):
  if b[i] == M:
    c.append(a[i])
if len(c) != 0:
  for i in range(M):
    if a[i] == 1:
      for j in range(len(c)):
        if b[i] == c[j]:
          print("POSSIBLE")
          exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int, input().split())
    x,y = [], []
    for _ in range(m):
        a,b = map(int, input().split())
        if a==1:
            x.append(b)
        if b==n:
            y.append(a)
    if not len(x)+len(y)==len(x+y):
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
data = [list(map(int, input().split())) for _ in range(m)]
start = set(i[1] for i in data if i[0] == 1)
goal = set(j[0] for j in data if j[1] == m)

if start & goal:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
data = [list(map(int, input().split())) for _ in range(m)]
start = set(i[1] for i in data if i[0] == data[0][0])
goal = set(j[0] for j in data if j[1] == data[-1][1])
if start & goal:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[[0,0]]*m
at=[0]*m
bt=[0]*m
atc=0
btc=0
a=False

f=0
for k in range(m):
  ln=list(map(int,input().split()))
  if ln[0]==1:
    at[atc]=ln[1]
    atc+=1
  elif ln[1]==n:
    bt[btc]=ln[0]
    btc+=1
del at[atc:]
del bt[btc:]
at.sort()
bt.sort()
c=list(set(at)&set(bt))
if len(c)!=(atc+btc):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[[0,0]]*m
t=[0]*m
tc=0
a=False
for k in range(m):
  l[k]=list(map(int,input().split()))
l.sort()
for k in l:
  if k[0]==1:
    t[tc]=k[1]
    tc+=1
  elif k[1]==n:
    if k[1] in t:
      a=True
      break
if a:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
a, b = [], []
c = 0
for i in range(m):
    ship1, ship2 = [int(i) for i in input().split()]
    if ship1 == 1:
        c = max(c, ship2)
    a.append(ship1)
    b.append(ship2)

d = 0
for i in range(m):
    ship1, ship2 = a[i], b[i]
    if ship1 == c and ship2 == n:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis1 = []
lis2 = []
ans = "IMPOSSIBLE"
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        lis1.append(b)
    else:
        lis2.append((a,b))
lis2 = set(lis2)        
for j in lis1:
    if (j,n) in lis2:
        ans = "POSSIBLE"
    else:
        pass
print(lis1,lis2)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def check():
    N,M = map(int, input().split())
    B = []
    hune = defaultdict(list)
    for _ in range(M):
        a,b = map(int, input().split())
        if a == 1:
            B.append(b)
        hune[a].append(b)
    print(hune[1])
    
    for b in B:
        for goal in hune[b]:
            if goal == N:
                print('POSSIBLE')
                return
    print('IMPOSSIBLE ')
    
check()

Submission status: Wrong Answer

Solution code:
def check():
    N,M = map(int, input().split())
    hune = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[0])
    print(hune)
    for a,b in hune:
        if a == 1:
            for c,d in hune:
                if c == b and d == N:
                    print('POSSIBLE')
                    return
        if a == 2:
            break
    print('IMPOSSIBLE')
check()

Submission status: Wrong Answer

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

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
for d in ab:
    print(d)
    if d[1] == N:
        c.append(d[0])


for d in ab:
    if d[1] in c and d[0] == 1:
        possible = True

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

Submission status: Wrong Answer

Solution code:
def check():
    N,M = map(int, input().split())
    hune = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[0])
    
    for a,b in hune:
        if a == 1:
            for c,d in hune:
                if c == b and d == N:
                    print('POSSIBLE')
                    return
        if a == 2:
            break
    print('POSSIBLE')
    
check()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = []
for i in range(M):
  a, b = map(int, input().split())
  L.append([a, b])
ans = 'IMPOSIBLE'
for l in L:
  if l[0] == 1:
    if [l[1], N] in L:
      ans = 'POSSIBLE'
      break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
from1 = set()
fromn = set()
a =[]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fromn.add(b)
    if b == n:
        from1.add(a)
if from1 and fromn:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
li = [list(map(int, input().split())) for n in range(M)]

a = []
b = []

for i in li:
  if i[1] == N:
    b.append(i[0])

  if i[0] == N:
    a.append(i[1])
    
if len(a) == 0 or len(b) == 0:
  print("IMPOSSIBLE")
  sys.exit()
    
    
for i in a:
  if i in b:
    print("IMPOSSIBLE")
    sys.exit()
    
print("POSSIBLE")

Submission status: Wrong Answer

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

a = []
b = []
for i in l:
    if i[0] == 1:
        a.append(i[1])
    if i[1] == n:
        b.append(i[0])

print("Possible" if len(set(a)&set(b)) > 0 else "Impossible")

Submission status: Wrong Answer

Solution code:
def takahasi(n , m , a):

    ans = "INPOSSIBLE"
    list1 = []
    listn = []

    for i in range(m):
        if a[i][0] == 1:
            list1.append(a[i][1])
        elif a[i][1] == n:
            listn.append(a[i][0])
    
    for i in range(len(list1)):
        if listn.count(list1[i]) != 0:
            ans = "POSSIBLE"

    return ans

def main():
    n , m = map(int , input().split())
    a = [list(map(int,input().split())) for i in range(m)]
    print(takahasi(n , m , a))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
print(aa)
print(bb)
list=set(aa) & set(bb)
print("IMPOSSIBLE" if len(list)==0 else "POSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("IMPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
print("IMPOSSIBLE" if set(aa)&set(bb)=='' else "POSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
	numa,numb=map(int,input().split())
	a.append(numa)
	b.append(numb)
bb=[]
aa=[]
if not 1 in a or not n in b:
	print("INPOSSIBLE")
	sys.exit()
for j in range(len(a)):
    if 1==a[j]:
        bb.append(b[j])
for k in range(len(b)):
    if n==b[k]:
        aa.append(a[k])
print("INPOSSIBLE" if set(aa)&set(bb)=='' else "POSSIBLE")

Submission status: Wrong Answer

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

ship_list = []
ans = "IMPOSSIBLE"

# 定期船の一覧をリストに格納
for i in range(m):
    ship_list.append(list(map(int, input().split())))
ship_list.sort(key=lambda x: (x[0], x[1]))

for i in range(m):
    if ship_list[i] == 1:
        for j in range(i, m):
            if ship_list[j][0] == ship_list[i][1] and ship_list[j][1] == n:
                ans = "POSSIBLE"
                break

print(ans)

Submission status: Wrong Answer

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

start = []
goal = []
for i in range(len(A)):
    if A[i][0] == '1':
        start.append(A[i])
    elif A[i][1] == str(N):
        goal.append(A[i])

is_ok = False
for j in range(len(start)):
    for k in range(len(goal)):
        if start[j][1] == goal[k][0]:
            is_ok = True
            break
    if is_ok:
        break

if is_ok:
    print('POSSIBLE')
else:
    print('INPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
f=set()
t=set()
for i in range(M):
  a,b=map(int,input().split())
  if a<2:
    f.add(b)
  if b==N:
    t.add(a)
print("IM"*len(f&t)+"POSSIBLE")

Submission status: Wrong Answer

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

for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    first.add(b)
  if b == N:
    second.add(a)

if first & second:
  print("POSSIBLE")
else:
  print("IMPOSSOBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
cu=[0]*200001
for i in range(m):
    x,y=map(int,input().split())
    cu[x]=y
f=cu[cu[1]]
print('POSSIBLE' if f==n else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
cu=[0]*2000001
for i in range(m):
    x,y=map(int,input().split())
    cu[x]=y
f=cu[cu[1]]
print('POSSIBLE' if f==n else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [0] * M
b = [0] * M
hub = []
for i in range(M):
    a[i], b[i] = map(int, input().split())
    if a[i] == N or b[i] == N:
        if a[i] == N:
            hub.append(b[i])
        else:
            hub.append(a[i])
# print(hub)
if len(hub) == 0:
    print('IMPOSSIBLE')
    exit()

for i in range(len(hub)):
    for j in range(M):
        # print(a[j],b[j])
        if a[j] == hub[i] or b[j] == hub[i]:
            if a[j] == hub[i] and b[j] == 1:
                print('POSSIBLE')
                exit()
            elif b[j] == hub[i] and a[j] == 1:
                print('POSSIBLE')
                exit()
            elif j == M-1:
                print('IMPOSSIBLE')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#AtCoder
from collections import defaultdict

N, M = map(int, input().split())
a = [list(map(int, input().split())) for i in range(M)]

d = defaultdict(list)

for e in a:
    d[e[0]].append(e[1])

sec = []
for key in d.items():
    if key[0] == 1:
        sec.append(key[1])

for key in d.items():
    if key[0] in sec[0]:
        if key[1][0] == N:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(m)]
print(a)
s=set()
for i in a:
    if i[1]==n:
        s.add(i[0])
for i in a:
    if i[0]==1 and i[1] in s:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import copy
N, M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]
mid = []
AB.sort()
CD = copy.deepcopy(AB)
CD.reverse()
for ab in AB:
    if ab[0] == 1:
        for  cd in CD:
            if cd[1] == N:
                if ab[1] == cd[0]:
                    print("POSSIBLE")
                    exit()
            else:
                break
    else:
        break
print("IMPOSSIBLE")

Submission status: Wrong Answer

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

ship_list1 = []
ship_list2 = []
count = 0

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i])
    if ab[i][1] == n:
        ship_list2.append(ab[i])

for ship1 in ship_list1:
    for ship2 in ship_list2:
        if ship1[1] == ship2[0]:
            print('POSSIBLE')
            count += 1
            break
        else:
            continue
    break

if count == 0:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

ship = []
count = 0

for i in range(m):
    if ab[i][1] == n:
        for j in range(m):
            if ab[i][0] == ab[j][1] and ab[j][0] == 1:
                print('POSSIBLE')
                count += 1
                break
            else:
                continue
        break
    else:
        continue

if count == 0:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
x = deque()
y = deque()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        x.append(b)
    elif b == n:
        y.append(a)
if len(x) < len(y):
    for i in x:
        if i in y:
            print('IMPOSSIBLE')
            exit()
    else:
        print('IMPOSSIBLE')
else:
    for i in y:
        if i in x:
            print('POSSIBLE')
            exit()
    else:
        print('IMPOSSIBLE')

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())
#     a.append(A)
#     b.append(B)
# graph = [list(map(int, input().split())) for _ in range(M)]
land = [[] for i in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    land[i - 1].append(j)
def landNumber(i,path):
    for j in range(len(land[i])):
        number=land[i][j]
        if path == 2:
            if number==N:
                print('POSSIBLE')
                exit()
            else:
                return
        else:
            if len(land[number-1]) == 0:
                continue
            else:
                landNumber(number - 1, path + 1)
    print('IMPOSSIBLE')
    exit()

if M == 1:
    print('IMPOSSIBLE')
    exit()
landNumber(0,1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
land = [[] for i in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    land[i - 1].append(j)
def landNumber(i,path):
    for j in range(len(land[i])):
        number=land[i][j]
        if path == 2:
            if number==N:
                print('POSSIBLE')
                exit()
            else:
                print('IMPOSSIBLE')
                exit()
        else:
            if len(land[number-1]) == 0:
                continue
            else:
                landNumber(number-1,path+1)

if M == 1:
    print('IMPOSSIBLE')
    exit()
landNumber(0,1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
land = [[] for i in range(N)]
for _ in range(M):
    i, j = map(int, input().split())
    land[i - 1].append(j)
def landNumber(i, j, path):
    for l in range(len(land[i])):
        number=land[i][l]
        if path == 2:
            if number==N:
                print('POSSIBLE')
                exit()
            else:
                print('IMPOSSIBLE')
                exit()
        else:
            if len(land[number-1]) == j:
                continue
            else:
                landNumber(number-1,0,path+1)

if M == 1:
    print('IMPOSSIBLE')
    exit()
landNumber(0,0,1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[list(map(int,input().split())) for i in range(m)]
lis=[]
for i in range(m):
  if g[i][0]==1:
    lis.append(g[i][1])
  if g[i][1]==n:
    lis.append(g[i][0])
lis.sort()
if len(lis)<2:
  print('IMPOSSIBLE')
else:
  for i in range(len(lis)-1):
    if lis[i]==lis[i+1]:
      print('POSSIBLE')
      exit()
  print('IMPOSSBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  ab.append((a,b))
#print(ab)

for i in range(n+1):
  if (1,i) in ab and (i,n) in ab:
    print("POSSIBLE")
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s1=set()
s2=set()
for _ in range(m):
  a,b=map(int,input().split())
  if a==1:
    s1.add(b)
  if b==n:
    s2.add(a)
if len(s1|s2)!=0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

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

from_1 = []
to_n = []

for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
      from_1.append(i)
    if a == n:
      to_n.append(i)
    if b == 1:
      from_1.append(i)
    if b == n:
        to_n.append(i)

if len(set(from_1) - set(to_n)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

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

from_1 = []
to_n = []

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

if len(set(from_1) - set(to_n)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
# グラフわからんのでグラフアルゴリズム忘れた
# dfsでやる 限度2回

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 dfs(t, c, used):
    if c == 0 and t == n - 1:
        return True
    if c == 0:
        return False
    flag = False
    for g in graph[t]:
        if g in used:
            continue
        next_used = used[:]
        next_used.append(g)
        flag = dfs(g, c - 1, next_used)
        if flag:
            break
    return flag


for x in graph[0]:
    if dfs(x, 2, [x]):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a = [[int(i) for i in input().split()] for i in range(m)] 
c=[]

print(a[0][0],a[0][1])
for i in range(m):
    if a[i][1] == n:
        c.append(a[i][0])
for i in range(m):
    if a[i][0]==1:
        if a[i][1] in c:
            print("POSSIBLE")
            sys.exit()
        
print("IMPOSSIBLE")

Submission status: Wrong Answer

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

rel = [[] for _ in [0]*(n+1)]

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

for i in range(n+1):
  if rel[i]:
    for r in rel[i]:
      if n in rel[r]:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)
  
if N==1:
  print("POSSIBLE")
  exit(0)

stack=[]
stack.append([0,2,-1])
while stack:
  node=stack.pop()
  v=node[0]
  ship=node[1]
  parent=node[2]
  if ship==N-1:
    print("POSSIBLE")
    break
  if ship<=0:
    continue
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,ship-1,v])
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)
  
if N==1:
  print("POSSIBLE")
  exit(0)

stack=[]
stack.append([0,2])
while stack:
  node=stack.pop()
  v=node[0]
  ship=node[1]
  if ship==N-1 and ship==0:
    print("POSSIBLE")
    break
  if ship<=0:
    continue
  childs=E[v]
  for child in childs:
    stack.append([child,ship-1])
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)
  
if N==1:
  print("POSSIBLE")
  exit(0)

stack=[]
stack.append([0,2])
while stack:
  node=stack.pop()
  v=node[0]
  ship=node[1]
  if ship==N-1:
    print("POSSIBLE")
    break
  if ship<=0:
    continue
  childs=E[v]
  for child in childs:
    stack.append([child,ship-1])
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)
  
stack=[]
stack.append([0,2])
while stack:
  node=stack.pop()
  v=node[0]
  ship=node[1]
  if ship==N-1:
    print("POSSIBLE")
    break
  if ship<=0:
    continue
  childs=E[v]
  for child in childs:
    stack.append([child,ship-1])
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
li.sort(key=lambda x:(x[0],x[1]))
mi = []
ma = []
for i in li:
    if i[0] == 1:
        mi.append(i[1])
    else:
        break
li = li[::-1]
for j in li:
    if j[1] == n:
        ma.append(j[0])
    else:
        break
for i in mi:
    if i  in ma:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")