Buggy python submission (verdict: Time Limit Exceeded):
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

import numpy as np
from numba import jit

N,Q = map(int,readline().split())
P = [tuple(map(int,readline().split())) for i in range(Q)]
P = np.array(P,dtype = int)

@jit('i8(i8,i8[:])')
def solve(N,P):
  ans = np.zeros(len(P), dtype = int)
  for i in range(len(P)):
    v = P[i][0] - 1
    w = P[i][1] - 1
    while v != w:
      if v > w:
        v = (v - 1) // N
      else:
        w = (w - 1) // N
    ans[i] = v + 1
  return ans

ans = solve(N,P)
for a in ans:
  print(a)


Fixed submission:
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  if N == 1:
    print(min(v,w))
    continue
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

def solve():
  for i in range(Q):
    v,w = map(int,readline().split())
    v -= 1
    w -= 1
    while v != w:
      if v > w:
        v = (v - 1) // N
      else:
        w = (w - 1) // N
    print(v + 1)

solve()

Fixed submission:
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  if N == 1:
    print(min(v,w))
    continue
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Fixed submission:
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  if N == 1:
    print(min(v,w))
    continue
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Buggy python submission (verdict: Time Limit Exceeded):
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Fixed submission:
# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  if N == 1:
    print(min(v,w))
    continue
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)