Problem:


Score : 300 points

Problem Statement

In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1, Island 2, ..., Island N.

There are M kinds of regular boat services between these islands.
Each service connects two islands. The i-th service connects Island a_i and Island b_i.

Cat Snuke is on Island 1 now, and wants to go to Island N.
However, it turned out that there is no boat service from Island 1 to Island N, so he wants to know whether it is possible to go to Island N by using two boat services.

Help him.

Constraints

3 ≤ N ≤ 200 000

1 ≤ M ≤ 200 000

1 ≤ a_i < b_i ≤ N

(a_i, b_i) \neq (1, N)

If i \neq j, (a_i, b_i) \neq (a_j, b_j).

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

If it is possible to go to Island N by using two boat services, print POSSIBLE; otherwise, print IMPOSSIBLE.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

POSSIBLE

Sample Input 2

4 3
1 2
2 3
3 4

Sample Output 2

IMPOSSIBLE

You have to use three boat services to get to Island 4.

Sample Input 3

100000 1
1 99999

Sample Output 3

IMPOSSIBLE

Sample Input 4

5 5
1 3
4 5
2 3
2 4
1 4

Sample Output 4

POSSIBLE

You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5.



Sample input:
3 2
1 2
2 3


Sample output:
POSSIBLE

Submission status: Wrong Answer

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

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]
    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")

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]
    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 dfs(1)[n] <=2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import collections

n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]

q = collections.deque()
q.append(1)

for k in range(2):
    for j in range(len(q)):
        tmp = q.pop()
        for i in s:
            if tmp in i:
                if tmp > i[0]:
                    q.append(i[0])
                else:
                    q.append(i[1])

if n in q:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import collections

n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]

q = collections.deque()
q.append(1)

for i in range(2):
    for j in range(len(q)):
        tmp = q.pop()
        for i in s:
            if tmp in i:
                if tmp > i[0]:
                    q.append(i[0])
                else:
                    q.append(i[1])

if n in q:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

ark={}
for i in range(m):
    a,b=map(int,input().split())
    ark[a]=b
    ark[b]=a

for i in range(2,n):
    if ark[1]==i and ark[i]==n:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

candidate = []
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        candidate.append(b)
    if b==n:
        if a in candidate:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
cnt = 0

while q:
    if cnt > 2:
        break
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)
    cnt += 1

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
cnt = 0

while q and cnt <= 2:
    cnt += 1
    node = q.popleft()
    after = graph[node]

    for a in after:
        q.append(a)
        if a == n:
            print("POSSIBLE")
            sys.exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
cnt = 0

while q and cnt < 2:
    cnt += 1
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
cnt = 0

while q and cnt <= 2:
    cnt += 1
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
cnt = 0

while q and cnt <= 2:
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)
    cnt += 1
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

contact = [[] for _ in range(N)]

for a, b in ab:
	contact[a-1].append(b-1)
	contact[b-1].append(a-1)

print(contact)

for x in contact[0]:
	if N-1 in contact[x]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Submission status: Wrong Answer

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

if m == 1:
  print("IMPOSSIBLE")

else:
  root = [[] for i in range(n)]
  for a, b in ab:
    root[a-1].append(b-1)
  
  flag = False
  for i in range(len(root)):
    for j in root[i]:
      if n-1 in root[j]:
        flag = True
        break

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

Submission status: Wrong Answer

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

if m == 1:
  print("IMPOSSIBLE")

else:
  root = [[] for i in range(n)]
  for a, b in ab:
    root[a-1].append(b-1)
  
  print(root)
  flag = False
  for i in range(len(root)):
    for j in root[i]:
      if n-1 in root[j]:
        flag = True
        break

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

Submission status: Wrong Answer

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

    if A == 1 :
        one.append(B)
    elif B == 1:
        one.append(A)

    if A == N or B == N:
        goal.append(A)
        goal.append(B)

print(one)
print(goal)

if set(goal) & set(one):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

    if A == 1 or B == 1:
        one.append(A)
        one.append(B)

    if A == M or B == M:
        goal.append(A)
        goal.append(B)
        

if set(goal) & set(one):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

    if A == 1: one.append(B)
    elif B == 1: one.append(A)
    
    if A == M: goal.append(B)
    elif B == M: goal.append(A)

if set(goal) & set(one):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def dfs(s):
    from collections import deque
    check = [0] * (n + 1)
    stack = deque([s])
    check[s] = 0
    while stack:
        now = stack.pop()
        for next in graph[now]:
            if check[next] != 0 and next != n:
                continue
            if next == n and check[now] == 1:
                print('POISSIBLE')
                exit()
            check[next] += check[now] + 1
            stack.appendleft(next)


dfs(1)
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):
  a,b=map(int,input().split())
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

dist=[-1 for i in range(n)]
dist[0]=0

dq=deque()
dq.append(0)

while dq:
  x=dq.popleft()

  if x==n-1:
    if dist[x]==2:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')
    exit()

  for i in tree[x]:
    if dist[i]==-1:
      dist[i]=dist[x]+1
      dq.append(i)

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):
  a,b=map(int,input().split())
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

dist=[-1 for i in range(n)]
dist[0]=0

dq=deque()
dq.append(0)

while dq:
  x=dq.popleft()

  if x==n-1:
    if dist[x]==2:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')

  for i in tree[x]:
    if dist[i]==-1:
      dist[i]=dist[x]+1
      dq.append(i)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc068/submissions/12987221
# C - Cat Snuke and a Voyage
import sys
import heapq

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

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

    def dfs(v, p):
        for u in edge[v]:
            if dist[u] != f_inf:
                continue
            else:
                dist[u] = min(dist[u], dist[v] + 1)
                dfs(u, v)

    dist = [f_inf] * n
    dist[0] = 0
    dfs(0, -1)

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


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,m=MI()
lis=[LI() for i in range(m)]
nums=[]
for i in range(m):
    if lis[i][0]==1:
        nums.append(lis[i][1])
    if lis[i][1]==n:
        nums.append(lis[i][0])
print(nums)
if len(nums)>len(list(set(nums))):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

    def dfs(G, v):
        seen = [False]*N
        todo = []
        seen[v] = True
        todo.append(v)
        dist = [10**9]*N
        dist[0] = 0
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                seen[next_v] = True
                dist[next_v] = dist[u] + 1
                todo.append(next_v)
        return dist

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

indexa_num = []
indexb_num = [x for x, v in enumerate(b) if v == n]
for i in indexb_num:
    indexa_num = [y for y, w in enumerate(a) if w == i]

ans = 'IMPOSSIBLE'
for j in indexa_num:
    if 1 == a[j]:
        ans = 'POSSIBLE'

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
cnt=0
for j in range(m):
  for k in range(m):
    if j==k:
      continue;
    else:
      a=set(lst[j])|set(lst[k])
      if len(a)==3 and 1 in a and n in a:
        cnt+=1
        exit()
if cnt>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N, M = map(int, readline().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, readline().split())
        path[a].append(b)
        path[b].append(a)
    print(path[1])
    print(path[N])
    if set(path[1])&set(path[N]):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

goto_N = [0]*N
from_1 = [0]*N

for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        from_1[b] = 1
    elif b == N:
        goto_N[a] = 1

for i in range(N):
    if goto_N[i] and from_1[i]:
        print("POSSIBLE")
        exit()

print("INPOSSIBLE")

Submission status: Wrong Answer

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

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])
print(abl1)
print(abl2)

for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
u=0
A=[]
B=[]
for i in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
for i in range(M):
  if A[i]==1:
    s=B[i]
    idxlist=[]
    for idx,val in enumerate(A):
      if val==s:
        idxlist.append(idx)
    for j in idxlist:
      if B[j]!=N:
        u+=1
if u==len(idxlist):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
p=tuple(tuple(map(int,input().split())) for _ in range (m))
s=set()
t=set()
for i in range(m):
    if 1 in p[i]:
        s.add(p[i][0])
        s.add(p[i][1])
    if n in p[i]:
        t.add(p[i][0])
        t.add(p[i][1])
res=s&t
if res:
    print("POSSIBLE")
else:
    print("INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
for o in one_li:
    if o in to_n_li:
        print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ma = [[False]*n for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    ma[a-1][b-1] = True
    ma[b-1][a-1] = True
flag = False
for row in ma:
    for i,r in enumerate(row):
        if r:
            if ma[i][n-1]:
                flag = True
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n,m = na()
g = [[] for i in range(n)]
for i in range(m):
    a,b = na()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

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

print('INPOSSIBLE')

Submission status: Wrong Answer

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

a = [0]*m
b = [0]*m
checks = [0]*n
checkg = [0]*n
for i in range(m):
    a[i],b[i] = map(int,input().split())
    if a[i]== 1:
        checks[b[i]]=1
    if b[i]== n:
        checkg[a[i]]=1
ans = 0
for i in range(n):
    if checks[i] == checkg[i] == 1:
        ans = 1
if ans :
    print("POSSIBLE")
else:
    print("IMPOSSIBILE")

Submission status: Wrong Answer

Solution code:

def main():
    n,m = map(int,input().split())
    ab = [[0] * n for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1][b-1] = 1

    for mid in range(1,n):
        if ab[0][mid] == 1 and ab[mid][n-1] == 1:
            return
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

print('IMPOSSIBLE' if len(set(an) & set(nb))==0 else 'POSSIBLE')

Submission status: Wrong Answer

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

flag = False
for i in range(len(ab)):
    for k in range(len(ab)-i):
        if len(set(ab[i])&set(ab[k]))==1:
            print('POSSIBLE')
            flag = True
            break
    if flag:
        break
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

flag = False
for i in range(len(ab)):
    for k in range(len(ab)-i):
        if len(list(set(ab[i])&set(ab[k])))==1:
            print('POSSIBLE')
            flag = True
            break
    if flag:
        break
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
li=[[]]*n
for i in range(m):
    a,b=map(int,input().split())
    li[a-1].append(b)
for j in li[0]:
    for k in li[j-1]:
        if k==n:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] == True
    if b == n:
        d[a] = True
for i in range(n):
    if c[i] and d[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

flag = False
for i in range(n):
    if graph[0][i] == 1:
        for j in range(n):
            if graph[i][j] == 1:
                flag = True
                break
                
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
a = 0
b = 1
mid = []
ab = []

n, m = map(int, input().split())
for i in range(m):
    ab.append(list(map(int, input().split())))
    if ab[i][a] == 1:
        mid.append(ab[i][b])

print(mid)

for _ab in ab:
    if _ab[b] == n and _ab[a] in mid:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l =[ list(map(int,input().split())) for i in range(m)]
l1 = set([i[1] for i in l if i[0]==1])
l2 = set([i[2] for i in l if i[0]==n])
l3 = l1&l2
if len(l3)>=1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
def main():
    n, m = input().split()
    g1 = []
    g2 = []
    for _ in range(int(m)):
        x, y = input().split()
        if x == 1:
            g1.append(y)
        elif y == n:
            g2.append(x)
    sx = set(g1)
    sy = set(g2)
    sxy = sx.intersection(sy)
    if len(sxy):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for x in l:
    if x[0] == 1:
        for y in l:
            if y[1] == n:
                print ("POSSIBLE")
                exit ()
print ("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
fr = {}
t = {}
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        fr[b] = 1
    if b == n:
        t[a] = 1

flag = False
for kk in t.keys():
    if kk in fr:
        flag = True
    break

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[0]*M;p=-1

for i in range(M):
  a,b=map(int,input().split())
  A[i]=a,b
A.sort(reverse=True,key=lambda x: x[1])
#print(A)
#print("Yes" if A[0][1]==N else "No")

if A[0][1]!=N:
  print("IMPOSSIBLE")
else:
  for i in range(1,M):
    if A[i][0]==1 and A[i][1]==A[0][0]:
      p=2
      #print(1,A[i][0],A[i][1],A[0][0],p)

  if p==2:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

a_list = []
tmp = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp.append(b)
    
    # 島1から意外の運航便のリスト
    else:
        a_list.append([a, b])

a_list.sort(key=lambda x: x[0])
tmp.sort()
#print(a_list)
#print(tmp)

possible = 0
break_on = 0
for b in tmp:
    #print(a_list)

    for j in range(len(a_list)):

        if a_list[j][0] < b:
            a_list.pop(j)

        elif a_list[j][1] == n:
            possible = 1
            break_on = 1
            break
        else:
            break
    
    if break_on == 1:
        break

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

Submission status: Wrong Answer

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

a_list = []
tmp = []
for i in range(m):
    a, b = map(int, input().split())
    
    # 島1から出ている船の行き先
    if a == 1:
        tmp.append(b)
    
    # 島1から意外の運航便のリスト
    else:
        a_list.append([a, b])

#a_list.sort(key=lambda x: x[0])
tmp.sort()
#print(a_list)
#print(tmp)

possible = 0
for b in tmp:
    #print(a_list)

    for j in range(len(a_list)):
        if len(a_list) == 1:
            if a_list[0][1] == n:
                possible = 1

        elif a_list[j][0] < b:
            a_list.pop(j)

        elif a_list[j][0] == b:
            if a_list[j][1] == n:
                possible = 1
                break
        else:
            break

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

Submission status: Wrong Answer

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

from_1=set([el[1] for el in ab if el[0]==1])
from_N=set([el[0] for el in ab if el[1]==N])
#print(from_1, from_N)
if from_1 & from_N:
    print('POSSIBLE')
else:
    print('IMPOSSILBE')

Submission status: Wrong Answer

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

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

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] < 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(m)]
A.sort()
aa = []
bb = []
for i in range(m):
    if A[i][0]==1 or i>0 and A[i][0] in bb:
        aa.append(A[i][0])
        bb.append(A[i][1])
        if bb[-1]==n and len(set(aa))<=2:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

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

l = [[0]*n for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  l[a-1][b-1] = 1
  l[b-1][a-1] = 1
#print(l)

for i in range(1,n):
  if l[0][i] == 1:
    if l[i][a-1] == 1:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    edges[b].append(a)
    # edges[b].append(a)
# print(edges)
# print(1,edges[1])
first = edges[1]
# print("----")
for e in first:
    # print(e,edges[e]) 
    second = edges[e]
    if N in second:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for i 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 x in g[0]:
  for y in g[x]:
    if y==n-1:
      print('POSSIBLE')
      exit()
print('No')

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
g=[[] for i 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 x in g[0]:
  for y in g[x]:
    if y==n-1:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(int)
for i in range(M):
    a,b = map(int, input().split())
    d[a] = b

for i,j in d.items():
    if i!=1:
        continue
    if (j,N) in d.items():
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
ab = []
for i in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
ab.sort(key=itemgetter(0))
print(ab)
fl = False
for i,j in ab:
    if i!=1:
        continue
    for k,l in ab:
        if i==1 and (j!=k or l!=N):
            continue
        else:
            fl = True
print('POSSIBLE') if fl else print('IMPOSSIBLE')

Submission status: Wrong Answer

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

N, M = MAP()
path = [LIST() for _ in range(M)]

# graph = [[] for _ in range(N)]

# for a, b in path:
# 	graph[a - 1].append(b - 1)
# 	graph[b - 1].append(a - 1)

# print(graph)

# for i in range(len(graph[0])):
# 	if graph[graph[0][i]][len(graph[graph[0][i]]) - 1] == N - 1:
# 		print("POSSIBLE")
# 		exit()

# print("IMPOSSIBLE")

graph = [[0]*N for _ in range(N)]

print(graph)

for i in range(M):
	graph[path[i][0] - 1][path[i][1] - 1] = 1
	graph[path[i][1] - 1][path[i][0] - 1] = 1

print(graph)

for i in range(N):
	if graph[0][i] == 1:
		if graph[i][N - 1] == 1:
			print("POSSIBLE")
			exit()

print("IMPOSSIBLE")

Submission status: Wrong Answer

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

N, M = MAP()
path = [LIST() for _ in range(M)]

b = [0]*N
graph = [b for _ in range(N)]

for i in range(M):
	graph[path[i][0] - 1][path[i][1] - 1] = 1
	graph[path[i][1] - 1][path[i][0] - 1] = 1

for i in range(N):
	if graph[0][i] == 1:
		if graph[i][N - 1] == 1:
			print("POSSIBLE")
			exit()

print("IMPOSSIBLE")