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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    N, M = map(int, readline().split())
    m = map(int, read().split())
    AB = list(zip(m, m))

    p1 = []
    p2 = []
    for a, b in AB:
        if a == 1:
            p1.append(b)
        if b == N:
            p2.append(a)

    if len(list(set(p1) & set(p2))) >= 1:
        print('POSSIVLE')
    else:
        print('IMPOSSIVLE')


main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]
ship = sorted(ship, key=lambda x: x[0])

if M == 1:
    print("IMPOSSIBLE")
    exit()

one = []
for i in range(N):
    if ship[0][0] == 1:
        one.append(ship[0])
        ship.pop(0)
    if ship[0][1] != N:
        ship.pop(0)

i = 0
while ship:
    if ship[0][0] == one[i][1]:
        if ship[0][1] == N:
            print("POSSIBLE")
            exit()

    i += 1
    if i == len(one):
        i = 0
        ship.pop(0)

print("IMPOSSHIBLE")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]
ship = sorted(ship, key=lambda x: x[0])

if M == 1:
    print("IMPOSSIBLE")
    exit()

one = []
while ship[0][0] == 1:
    one.append(ship[0])
    ship.pop(0)

i = 0
while ship:
    if ship[0][0] == one[i][1]:
        if ship[0][1] == N:
            print("POSSIBLE")
            exit()

    i += 1
    if i == len(one):
        i = 0
        ship.pop(0)

print("IMPOSSHIBLE")

Submission status: Wrong Answer

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

flag = False

c1 = [False] * (n + 1)
c2 = [False] * (n + 1)

for i in range(m):
    fd = r[i] // 10  # first digit
    sd = r[i] - r[i] // 10 * 10  # second digit
    if fd == 1:  # 島1との定期便があるか
        c1[sd] = True
    if sd == n:  # 島Nとの定期便があるか
        c2[fd] = True

# print(c1, c2)

for i in range(n + 1):
    if c1[i] and c2[i]:
        flag = True
        break

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
li = []
numb = []
ans = ''
for i in range(M):
  li.append(tuple(map(int,input().split())))
  if li[i][0] == 1:
    numb.append(i)
for i in range(M):
  if li[i][0] in numb and li[i][1] == N:
    ans = 'POSSIBLE'
    break
if ans == '':
  print('IMPOSSIBLE')
else:
  print(ans)

Submission status: Wrong Answer

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

L=[[0]*2 for i in range(M)]

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

A=[10**10]*M
B=[10**10]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break

for i in A:
    if i == 10**10 : 
        print("IMPOSSIBLE")
        exit()
        
    for j in B:
        if i == j:
            print("POSSIBLE")
            exit()
        if j == 10**10 : break

Submission status: Wrong Answer

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

L=[[0]*2 for i in range(M)]

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

A=[10**10]*M
B=[10**10]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break

for i in A:
    for j in B:
        if i == j:
            print("POSSIBLE")
            exit()
        if j == 10**10 : break
    if i == 10**10 : 
        print("IMPOSSIBLE")
        exit()

Submission status: Wrong Answer

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

L=[[0]*2 for i in range(M)]

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

A=[10**10]*M
B=[10**10]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break

for i in A:
    for j in B:
        if i == j:
            print("POSSIBLE")
            exit()
        if j == 10**10 : break
    if j == 10**10 : 
        print("IMPOSSIBLE")
        exit()

Submission status: Wrong Answer

Solution code:
n, m, *ab = [int(x) for x in open(0).read().split()]

from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] * 2):
    if a == 1: from_1.add(b)
    if b == n: to_n.add(a)
print('POSSIBLE' if from_1 and to_n else "IMPOSSIBLE")

# 大嘘。これで通ったら...

Submission status: Wrong Answer

Solution code:
n, m, *ab = [int(x) for x in open(0).read().split()]

from_1, to_n = set(), set()
for a, b in zip(*[iter(ab)] * 2):
    if a == 1: from_1.add(b)
    elif b == n: to_n.add(a)
print('POSSIBLE' if from_1 and to_n else "IMPOSSIBLE")

# 大嘘。これで通ったら...

Submission status: Wrong Answer

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

via = []
for i, v in enumerate(sorted(boat)):
    if v[0] == 1:
        via.append(v[1])
    else:
        break

flag = False
for b in sorted(boat, key=lambda x: x[1], reverse=True):
    if b[0] in via:
        flag = True
        break

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

Submission status: Wrong Answer

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

print(sorted(boat))

via = []
for i, v in enumerate(sorted(boat)):
    if v[0] == 1:
        via.append(v[1])
    else:
        break

flag = False
for v in via:
    if [v, N] in boat:
        flag = True
        break

if flag:
    print("POSSIBLE")
else:
    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:
    sa.add(b)
  if b == n:
    sb.add(a)

if sa&sb == 0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
from collections import defaultdict 
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    d[a].append(b)
    d[b].append(a)
q=[0]
dist=[0]*n 
vis=[0]*n 
vis[0]=1 
while q:
    t=q.pop(0)
    for i in d[t]:
        if not vis[i]:
            vis[i]=1 
            dist[i]=dist[t]+1 
            q.append(i)
print('POSSIBLE' if dist[n-1]<=2 else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
# ABC068 C - Cat Snuke and a Voyage
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,m = nm()
G = [[] for _ in range(n)]

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

# print(G)

for g in G:
    island_1toi = False
    island_iton = False
    for gg in g:
        if gg == 1:
            island_1toi = True
        if gg == n-1:
            island_iton = True

        if island_1toi == True and island_iton == True:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

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

Ship1 = []
Ship2 = []

for i in Ship:
    if i[0] == 1:
        Ship1 += [i[1]]
    elif i[1] == n:
        Ship2 += [i[0]]
if set(Ship1) and set(Ship2):#もし同じ値があったらPOSSIBLE、なかったらINPOSSIBLEと表示させる
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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

Ship1 = []
Ship2 = []

for i in Ship:
    if i[0] == 1:
        Ship1 += [i[1]]
    elif i[1] == n:
        Ship2 += [i[0]]
if set(Ship1) and set(Ship2):#もし同じ値があったらPOSSIBLE、なかったらINPOSSIBLEと表示させる
    print("POSSIBLE")
else:
    print("INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
def main():
    n,m=map(int,input().split(' '))
    ship=[[i for i in list(map(int,input().split(' ')))] for j in range(m)]
    sorted_ship=sorted(ship)
    rev_ship=sorted(ship,reverse=True)
    mid=[]
    for i in sorted_ship:
        if i[0] != 1:
            break
        mid.append(i[1])
    for i in rev_ship:
        if i[1] != n:
            break
        if i[0] in mid:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 'IMPOSSIBLE'

for i in range(2, n):
  path = [1, i, n]
  #if len([True for x in zip(path, path[1:]) if x in cand_path])==2:
   # ans = 'POSSIBLE'
    #break
  
  
print(ans)

Submission status: Wrong Answer

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

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

flag = False

for i in ab[0]:
    try:
        if ab[i][0] == n-1:
            flag = True
    except:
        continue

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
way=sorted([input().split() for _ in range(M)])
b=set(way[x][0] for x in range(M) if way[x][1]==str(N))
a=set(way[x][1] for x in range(M) if way[x][0]=='1')
for i in a:
    for j in b:
        if [i,j] in way:
            print('POSSIBLE')
            exit()          
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
way=sorted([input().split() for _ in range(M)])
b=set(way[x][0] for x in range(M) if way[x][1]==str(N))
a=set(way[x][1] for x in range(M) if way[x][0]=='1')
for i in a:
    for j in b:
        for k in range(M):
            if way[k]==[i,j]:
                print('POSSIBLE')
                exit()          
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
way=sorted([input().split() for _ in range(M)])
b=set(way[x][0] for x in range(M) if way[x][1]==str(N))
a=set(way[x][1] for x in range(M) if way[x][0]=='1')
for i in a:
    for j in range(M):
        if way[j][0]==i:
            for k in b:
                if way[j][1]==k:
                    print('POSSIBLE')
                    exit()              
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
way=sorted([input().split() for _ in range(M)])
b=set(way[x][0] for x in range(M) if way[x][1]==str(N))
a=set(way[x][1] for x in range(M) if way[x][0]=='1')
for i in a:
    for j in range(M):
        for k in b:
            if way[j][0]==i and way[j][1]==k:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
##############################

from collections import deque

N, M = map(int, input().split())
cost = [ [] for _ in range(N) ]
visited = [False] * N

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

#print(cost)

def bfs(node, dist):
    d = deque()
    d.append( (node, dist) )

    while d:
        (node, dist) = d.popleft()
        visited[node] = True

        for i in cost[node]:
            d.append((i, dist+1))

    return dist


if bfs(0, 0) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
a = [sorted(map(int,input().split())) for _ in range(m)]
print("POSSIBLE" if [1,n-1] in a and [n-1,n] in a else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
V, E_num = map(int, input().split())

E    = []


for i in range(E_num):
    a, b = map(int, input().split())
    E.append({a, b})

flg = 1

for i in range(V):

    if {1, i} in E:
        for j in range(V):
            if {i, j} in E and not {1, j} in E:
                print("IMPOSSIBLE")
                break
                flg = 0
    if flg==1:
        break

if flg == 1:
    print("POSSIBLE")

Submission status: Wrong Answer

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

atb  = [list(map(int, input().split())) for _ in range(M)]

flg  = 0
#愚直にやる
for i in range(2, N, 1):

    #定期便ある?
    if [1, i] in atb:
        print(1, i)
        if [i, N] in atb:
            print("POSSIBLE")
            flg = 1
if flg==0:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dfs(now,prev,count):
    global flag
    flag=False
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if count<=2:
            if next != prev:
                if next== n-1:
                    if count==2:
                        flag=True
                        break
                    else:
                        break
                dfs(next,now,count)
 
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
dfs(0,-1,0)
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**9)

def dfs(now,prev,count):
    global flag
    flag=False
    # 今いる頂点から行ける頂点を順に next に入れてループ
    count+=1
    for next in g[now]:
        if next != prev:
            if next== n-1:
                if count==2:
                    flag=True
                    break
                else:
                    break
            dfs(next,now,count)
 
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
dfs(0,-1,0)
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Submission status: Wrong Answer

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

g = [[ ] for i in range(n+1)]

for i in range(m):
    a,b = map(int,input().split())
    bisect.insort(g[a],b)
    bisect.insort(g[b],a)
    #print(bisect.bisect_left(g[a],b))
    #g[a][] = b
    #g[a].append(b)
    #g[b].append(a)

if len(g[n]) == 0:
    print('IMPOSSIBLE')
    exit()

for i in g[n]:
    if g[i][0] == 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
c = [False] * N
d = [False] * N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        c[b - 1] = True
    if b == N:
        d[a - 1] = True
ans = any([c[i] and d[i] for i in range(N)])
print("POSSIBLE" if ans else "INPOSSIBLE")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
A = []
B = []
flag = False
for _ in range(m):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)
indexes = [i for i,x in enumerate(A) if x==1]
for j in range(len(indexes)):
  if B[indexes[j]] in A:
    if B[A.index(B[indexes[j]])]==n:
      flag = True
      break
print('POSSIBLE' if flag==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)]

o = float('inf')
for x in ab:
    if n in x:
        if x.index(n) == 0:
            o = x[1]
        else:
            o = x[0]

for a, b in ab:
    if a == o:
        if b == 1:
            print('POSSIBLE')
            exit()
    if b == o:
        if a == 1:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]
secondship=[]
matchedship=[]
for n in range(M):
  if S[n][2]==str(N):
    secondship.append(S[n])
if len(secondship) == 0:
  print('IMPOSSIBLE')
  exit()
for v in secondship:
  for i in range(M):
    if S[i][0] =='1' and S[i][2] == v[0]:
      matchedship.append(S[i])
if len(matchedship) != 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]
secondship=[]
for n in range(M):
  if S[n][2]==str(N):
    secondship.append(S[n])
if len(secondship) == 0:
  print('IMPOSSIBLE')
  exit()
for v in secondship:
  for i in range(M):
    if S[i][0] =='1' and S[i][2] == v[0]:
      print('POSSIBLE')
      exit()

print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]
secondship=[]
for n in range(M):
  if S[n][2]==str(N):
    secondship.append(S[n])
for v in secondship:
  for i in range(M):
    if S[i][0] =='1' and S[i][2] == v[0]:
      print('POSSIBLE')
      exit()
    
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N,M = input().split(" ")
N,M=int(N),int(M)
S=[input() for i in range(M)]
startship=[]
for i in range(M):
  if S[i][0]=='1':
    startship.append(S[i])
for n in range(len(startship)):
  if S[n][2]==str(N):
    print('POSSIBLE')
    exit()
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==1:sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Submission status: Wrong Answer

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

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

if 1 not in D.keys():
  print ("IMPOSSIBLE")
else:
  if D[1] not in D.keys():
    print ("IMPOSSIBLE")
  elif D[D[1]] == N:
    print ("POSSIBLE")
  else:
    print ("IMPOSSIBLE")

Submission status: Wrong Answer

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

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

if 1 not in D.keys():
  print ("IMPOSSIBLE")
else:
  if D[1] not in D.keys():
    print ("IMPOSSIBLE")
  elif D[D[1]] == N:
    print ("POSSIBLE")

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
ls = []
heapq.heapify(ls)
for i in range(m):
    if ab[i][0] == 1:
        heapq.heappush(ls, ab[i][1])
    else:
        while True:
            if len(ls) != 0:
                p = heapq.heappop(ls)
                if p == ab[i][0]:
                    if ab[i][1] == n:
                        print("POSSIBLE")
                        exit()
                    else:
                        heapq.heappush(ls, p)
                        break
                elif p > ab[i][0]:
                    heapq.heappush(ls, p)
                    break

            else:
                print("IMPOSSIBLE")
                exit()

Submission status: Wrong Answer

Solution code:
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
ls = []
heapq.heapify(ls)
for i in range(m):
    if ab[i][0] == 1:
        heapq.heappush(ls, ab[i][1])
    else:
        while True:
            if len(ls) != 0:
                p = heapq.heappop(ls)
                if p == ab[i][0]:
                    if ab[i][1] == n:
                        print("POSSIBLE")
                        exit()
                elif p > ab[i][0]:
                    heapq.heappush(ls, p)
                    break
            else:
                break
print("IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
B=[list(map(int,input().split())) for _ in range(M)]
li=[]
ans="INPOSSIBLE"
for i,j in B:
  if i==1:
    li.append(j)
for l in li:
  if l==N:
    ans="POSSIBLE"
  else:
    for i,j in B:
      if i==l and j==N:
        ans="POSSIBLE"
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ships = [[] for _ in range(2*10**5+1)]
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  if _to == N:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ships = [[]] * (2*10**5+1)
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  for _dist in ships[_to]:
    if _dist == N:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ships = [[]] * (2*10**5+1)
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  if _to == N:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    for i in range(M):
        a,b = inputMap()
        ab.append((a,b))
        
    UF = WeightedUnionFind(N)
    
    for i,val in enumerate(ab):
        a,b = val
        UF.union(a-1,b-1,1)
        
    flg = UF.is_same(0, N-1)
    if flg == False:
        print("IMPOSSIBLE")
    else:
        tmp = UF.diff(0, N-1)
        if tmp >= 0:
            if tmp <= 2:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        else:
            if tmp >= -2:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        
class WeightedUnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		# 親への重みを管理
		self.weight = [0 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			y = self.find(self.par[x])
			# 親への重みを追加
			self.weight[x] += self.weight[self.par[x]]
			self.par[x] = y
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y, w):
		rx = self.find(x)
		ry = self.find(y)
		# xの木の高さ < yの木の高さ
		if self.rank[rx] < self.rank[ry]:
			self.par[rx] = ry
			self.weight[rx] = w - self.weight[x] + self.weight[y]
		# xの木の高さ ≧ yの木の高さ
		else:
			self.par[ry] = rx
			self.weight[ry] = -w - self.weight[y] + self.weight[x]
			# 木の高さが同じだった場合の処理
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] += 1
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
	# x から yへの重みは？
	def diff(self, x, y):
		return self.weight[x] - self.weight[y]

    
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    for i in range(M):
        a,b = inputMap()
        ab.append((a,b))
        
    UF = WeightedUnionFind(N)
    
    for i,val in enumerate(ab):
        a,b = val
        UF.union(a-1,b-1,1)
        
    flg = UF.is_same(0, N-1)
    if flg == False:
        print("IMPOSSIBLE")
    else:
        tmp = UF.diff(0, N-1)
        if tmp >= 0:
            if tmp <= 2:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        else:
            if tmp <= -2:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        
class WeightedUnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		# 親への重みを管理
		self.weight = [0 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			y = self.find(self.par[x])
			# 親への重みを追加
			self.weight[x] += self.weight[self.par[x]]
			self.par[x] = y
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y, w):
		rx = self.find(x)
		ry = self.find(y)
		# xの木の高さ < yの木の高さ
		if self.rank[rx] < self.rank[ry]:
			self.par[rx] = ry
			self.weight[rx] = w - self.weight[x] + self.weight[y]
		# xの木の高さ ≧ yの木の高さ
		else:
			self.par[ry] = rx
			self.weight[ry] = -w - self.weight[y] + self.weight[x]
			# 木の高さが同じだった場合の処理
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] += 1
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
	# x から yへの重みは？
	def diff(self, x, y):
		return self.weight[x] - self.weight[y]

    
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    for i in range(M):
        a,b = inputMap()
        ab.append((a,b))
        
    UF = WeightedUnionFind(N)
    
    for i,val in enumerate(ab):
        a,b = val
        UF.union(a-1,b-1,1)
        
    flg = UF.is_same(0, N-1)
    if flg == False:
        print("IMPOSSIBLE")
    else:
        tmp = UF.diff(0, N-1)
        if tmp <= 2:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        
class WeightedUnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		# 親への重みを管理
		self.weight = [0 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			y = self.find(self.par[x])
			# 親への重みを追加
			self.weight[x] += self.weight[self.par[x]]
			self.par[x] = y
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y, w):
		rx = self.find(x)
		ry = self.find(y)
		# xの木の高さ < yの木の高さ
		if self.rank[rx] < self.rank[ry]:
			self.par[rx] = ry
			self.weight[rx] = w - self.weight[x] + self.weight[y]
		# xの木の高さ ≧ yの木の高さ
		else:
			self.par[ry] = rx
			self.weight[ry] = -w - self.weight[y] + self.weight[x]
			# 木の高さが同じだった場合の処理
			if self.rank[rx] == self.rank[ry]:
				self.rank[rx] += 1
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
	# x から yへの重みは？
	def diff(self, x, y):
		return self.weight[x] - self.weight[y]

    
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

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)
H = deque()
H.append(0)
visited = [0]*N
visited[0] = 1

while (4 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:
#!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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    print("ABC"+str(n))
    return

#B
def B():
    ni = [2 ** i for i in range(1, 10)]
    n = II()
    ans = 1
    for i in range(1, n + 1):
        if i in ni:
            ans = i
    print(ans)        
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    next = []
    for i in edg[0]:
        next.append(i)
    for ne in next:
        if ne == n-1:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Wrong Answer

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

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
visited[0] = 1

while (4 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")