Problem:


Score : 100 points

Problem Statement

You are given an integer N. Consider an infinite N-ary tree as shown below:

Figure: an infinite N-ary tree for the case N = 3

As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1. For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.

Regarding this tree, process Q queries. The i-th query is as follows:

Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i.

Notes

In a rooted tree, the lowest common ancestor (LCA) of Vertex v and w is the farthest vertex from the root that is an ancestor of both Vertex v and w. Here, a vertex is considered to be an ancestor of itself. For example, in the tree shown in Problem Statement, the LCA of Vertex 5 and 7 is Vertex 2, the LCA of Vertex 8 and 11 is Vertex 1, and the LCA of Vertex 3 and 9 is Vertex 3.

Constraints

1 ≤ N ≤ 10^9

1 ≤ Q ≤ 10^5

1 ≤ v_i < w_i ≤ 10^9

Input

Input is given from Standard Input in the following format:

N Q
v_1 w_1
:
v_Q w_Q

Output

Print Q lines. The i-th line (1 ≤ i ≤ Q) must contain the index of the lowest common ancestor of Vertex v_i and w_i.

Sample Input 1

3 3
5 7
8 11
3 9

Sample Output 1

2
1
3

The queries in this case correspond to the examples shown in Notes.

Sample Input 2

100000 2
1 2
3 4

Sample Output 2

1
1



Sample input:
3 3
5 7
8 11
3 9


Sample output:
2
1
3

Submission status: Time Limit Exceeded

Solution code:
import math
N, Q = map(int, input().split())

def getdep(x):
   mul, val, d = 1, 0, 1
   while (val + mul < x):
      val += mul
      mul *= N
      d += 1
   return d
def up(x):
   if (x % N == 0):
      return x // N
   elif (x % N == 1):
      return (x - 1) // N
   else:
      return (x - (x % N)) // N + 1
for i in range(0, Q):
   u, v = map(int, input().split())
   if (N == 1) :
      print (min(u, v))
   else :
      if (u < v): u, v = v, u
      d1, d2 = getdep(u), getdep(v)
      for i in range(0, d1 - d2):
         u = up(u)
      while (u != v):
         u, v = up(u), up(v)
      print (u)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
def get_parent(child,n):
    parent = 0
    if(child%n <= 1):
        parent = (child)//n
    else:
        parent = child//n + 1
    return parent
    


n, q = list(map(int,input().split()))


if(n == 1):
    for i in range(q):
        v, w = list(map(int,input().split()))
        print(min(v,w))
else:
    for i in range(q):
        v, w = list(map(int,input().split()))
        hv, hw = -1, -1
        vparent, wparent = v, w
        while(wparent!=vparent):
            if(wparent>vparent):
                wparent = get_parent(wparent,n)
            else:
                vparent = get_parent(vparent,n)
        print(wparent)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
def get_parent(child,n):
    parent = 0
    if(child%n <= 1):
        parent = (child)//n
    else:
        parent = child//n + 1
    return parent
    


n, q = list(map(int,input().split()))


if(n == 1):
    for i in range(q):
        v, w = list(map(int,input().split()))
        print(min(v,w))
else:
    right = [0 for i in range(int(math.log(10**9,n)+2))]
    for i in range(len(right)):
        right[i] = (n**(i+1)-1)//(n-1)
    #print(right)
        
    for i in range(q):
        v, w = list(map(int,input().split()))
        hv, hw = -1, -1
        vparent, wparent = v, w
        for j,r in enumerate(right):
            if(hv == -1 and v<=r):hv = j
            if(hw == -1 and w<=r):hw = j
        for j in range(abs(hw-hv)):
            if(hw>hv):
                wparent = get_parent(wparent,n)
            elif(hv>hw):
                vparent = get_parent(vparent,n)
        while(wparent!=vparent):
            wparent = get_parent(wparent,n)
            vparent = get_parent(vparent,n)
        print(wparent)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
def get_parent(child,n):
    parent = 0
    if(child%n == 1):
        parent = (child-1)//n
    elif(child%n == 0):
        parent = child//n
    else:
        parent = child//n + 1
    return parent
    


n, q = list(map(int,input().split()))


if(n == 1):
    for i in range(q):
        v, w = list(map(int,input().split()))
        print(min(v,w))
else:
    right = [0 for i in range(int(math.log(10**9,n)+2))]
    for i in range(len(right)):
        right[i] = (n**(i+1)-1)//(n-1)
    
    for i in range(q):
        v, w = list(map(int,input().split()))
        hv, hw = -1, -1
        vparent, wparent = v, w
        for i,r in enumerate(right):
            if(hv == -1 and v<=r):hv = i
            if(hw == -1 and w<=r):hw = i
        for i in range(abs(hw-hv)):
            if(hw>hv):
                wparent = get_parent(wparent,n)
            elif(hv>hw):
                vparent = get_parent(vparent,n)
        while(wparent!=vparent):
            wparent = get_parent(wparent,n)
            vparent = get_parent(vparent,n)
        print(wparent)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
c = 1
B = [1]
ans = []
append = ans.append
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, readline().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v + (N - 2)) // N
        w = (w + (N - 2)) // N
    append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from sys import stdin
readline = stdin.readline
N, Q = map(int, readline().split())
c = 1
B = [1]
ans = []
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, readline().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    ans.append(str(v))
print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from sys import stdout
N, Q = map(int, input().split())
c = 1
B = [1]
ans = []
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, input().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    ans.append(str(v))
print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
N, Q = map(int, input().split())
c = 1
B = [1]
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, input().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    if lv < lw:
        w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    print(v)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
N, Q = map(int, input().split())
c = 1
B = [1]
while c < 10**9:
    B.append(c+1)
    c = c*N + 1
for q in range(Q):
    v, w = map(int, input().split())
    lv = bisect(B, v)
    lw = bisect(B, w)
    for i in range(lv, lw):
        w = (w - 2 + N) // N
    while v != w:
        v = (v - 2 + N) // N
        w = (w - 2 + N) // N
    print(v)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
N,Q = map(int,raw_input().split())
if N == 1:
  for i in range(Q):
    a,b = map(int,raw_input().split())
    print(min(a,b))
  sys.exit()

MAXN = 10**9
borders = [1]
while borders[-1] < MAXN:
  borders.append(borders[-1] + N**(len(borders) - 1))

def pos(a):
  rank = bisect.bisect_right(borders, a) - 1
  idx = a - borders[rank]
  return (rank,idx)

def parent(p):
  rank,idx = p
  return (rank-1, idx//N)

for i in range(Q):
  a,b = map(int,raw_input().split())
  p1,p2 = pos(a),pos(b)
  while p1 != p2:
    if p1 > p2:
      p1 = parent(p1)
    else:
      p2 = parent(p2)
  rank,idx = p1
  print(borders[rank] + idx)

Submission status: Time Limit Exceeded

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

if N == 1:
    for i in range(Q):
        V, W = map(int, input().split())
        print(min(V, W))
else:
    p = []
    p.append(1)
    for i in range(40):
        p.append(p[-1] * N)

    for i in range(Q):
        V, W = map(int, input().split())

        v = []
        w = []
        dv = 0
        dw = 0

        while V > (p[dv + 1] - 1) // (N - 1): dv = dv + 1
        while W > (p[dw + 1] - 1) // (N - 1): dw = dw + 1

        v.append(V)
        e = V
        for j in range(dv, 0, -1):
            e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1;
            v.append(e)
        v.reverse()

        w.append(W)
        e = W
        for j in range(dw, 0, -1):
            e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1;
            w.append(e)
        w.reverse()

        ans = 1
        j = 0
        while j < len(v) and j < len(w) and v[j] == w[j]:
            ans = v[j]
            j = j + 1
        print(ans)

Submission status: Accepted

Solution code:
# 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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
VW = [tuple(map(int,input().split())) for i in range(Q)]

ans = []
if N==1:
    for v,w in VW:
        ans.append(min(v,w))
else:
    for v,w in VW:
        while v != w:
            if v > w: v,w = w,v
            w = (w+N-2)//N
        ans.append(v)
print(*ans, sep='\n')

Submission status: Accepted

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

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

if N == 1:
    ans = [min(map(int, input().split())) for _ in range(Q)]
    print(*ans, sep="\n")
    exit()

ans = [-1] * Q
for i in range(Q):
    x, y = map(int, input().split())
    x_memo = [x]
    y_memo = [y]
    while x:
        x = (x + N - 2) // N
        x_memo.append(x)
    while y:
        y = (y + N - 2) // N
        y_memo.append(y)

    res = -1
    while x_memo and y_memo:
        xi = x_memo.pop()
        yi = y_memo.pop()
        if xi == yi:
            res = xi
        else:
            break
    ans[i] = res

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
N,Q=map(int,input().split())
if N>1:
    def find_par(x):
        u=x%N-1
        if u<=0:
            u+=N
        return (x-u-1)//N+1
    def path(x):
        s_node=x
        d=[s_node]
        while s_node!=1:
            s_node=find_par(s_node)
            d.append(s_node)
        return d
    for _ in range(Q):
        v,w=map(int,input().split())
        data1=set(path(v))
        data2=set(path(w))
        print(max(data1 & data2))
else:
    for _ in range(Q):
        v,w=map(int,input().split())
        print(min(v,w))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    if n==1:
        print(min(u,v))
        continue
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(((u-1)//n)-1)//n
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(((v-1)//n)-1)//n
            else:
                v=(v-1)//n
    print(u+1)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    if n==1:
        for a,b in ab:
            print(min(a,b))
        return
    for a,b in ab:
        while a!=b:
            if a<b:
                b=(b+n-2)//n
            else:
                a=(a+n-2)//n
        print(a)
    
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

ans = ""
n, q = [int(item) for item in input().split()]
if n == 1:
    for i in range(q):
        v, w = [int(item) for item in input().split()]
        print(min(v, w))
    exit()

for i in range(q):
    v, w = [int(item) - 1 for item in input().split()]
    while v != w:
        if v > w:
            v = (v - 1) // n
        else:
            w = (w - 1) // n
    print(v + 1)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
if n==1:
    for i in range(q):
        v,w=map(int,input().split())
        print(min(v,w))
else:
    for i in range(q):
        v,w=map(int,input().split())
        while v!=w:
            if v>w:v,w=w,v
            w=(w+n-2)//n
        print(v)

Submission status: Accepted

Solution code:
import sys
def main():
    def input():
        return sys.stdin.readline()[:-1]
    N, Q = map(int,input().split())
    ans = []
    if N == 1:
        for k in range(Q):
            v, w = map(int,input().split())
            ans.append(min(v,w))
    else:
        for k in range(Q):
            v, w = map(int,input().split())
            while v!=w:
                if v > w:
                    v, w = w, v
                w = (w+N-2)//N
            ans.append(v)
    print(*ans,sep="\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n, q = [ int(v) for v in input().split() ]

if n != 1:
    tree_list = [0] + [ (n**(i+1)-1) // (n-1) for i in range(100) if (n**(i+1)-1) // (n-1) <= 10**9 ]

def upward(a):
    d = bisect.bisect_left(tree_list,a) - 1
    outlist = []
    for i in range(d+1):
        outlist.append(a)
        if i < d:
            a -= tree_list[d-i] + 1
            a //= n
            a += tree_list[d-i-1] + 1
    return d, outlist

def lca(a,b):
    da, a_list = upward(a)
    db, b_list = upward(b)

    if da < db:
        da, db = db, da
        a_list, b_list = b_list, a_list
    s = da - db
    ans = None
    for i in range(db+1):
        if a_list[s+i] == b_list[i]:
            ans = a_list[s+i]
            break
    return ans



for i in range(q):
    v, w = [ int(v) for v in input().split() ]
    if n != 1:
        print(lca(v,w))
    else:
        print(min(v,w))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, q = LI()




for i, j in LIR(q):
    if n == 1:
        print(min(i, j))
    else:
        while i != j:
            if i < j:
                i, j = j, i
            i = (i - 2) // n + 1
        print(i)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
queries = []
for i in range(Q):
    v, w = map(int, input().split())
    queries.append([v, w])

if N == 1:
    for v, w in queries:
        print(min(v, w))
else:
    for v, w in queries:
        if 1 in [v, w]:
            print(1)
        else:
            # v < w にする
            v, w = min(v,w), max(v, w)
            v -= 2
            w -= 2
            v_parents = [v]
            isReported = False
            while v > 0:
                v_parents.append(v // N - 1)
                v = v//N-1
            while w > 0:
                w = w // N-1
                if w in v_parents:
                    print(w+2)
                    isReported = True
                    break
            if not isReported:
                print(1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,Q = map(int,input().split())
V,W = np.array([input().split() for _ in range(Q)],dtype=np.int64).T

if N == 1:
    answer = np.minimum(V,W)
else:
    for _ in range(50):
        V[V>W] = (V[V>W]+N-2)//N
        W[W>V] = (W[W>V]+N-2)//N
    answer = V

print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
 while n>1and v!=w:
  if v>w:v,w=w,v
  w=(w+n-2)//n
 print(v)

Submission status: Accepted

Solution code:
n,q,*t=map(int,open(0).read().split())
for v,w in zip(t[::2],t[1::2]):
 if~-n:
  while v!=w:
   if v>w:v,w=w,v
   w=(w+n-2)//n
 print(v)

Submission status: Accepted

Solution code:
def main():
  n,q,*t=map(int,open(0).read().split())
  for v,w in zip(t[::2],t[1::2]):
    if n<2:
      print(min(v,w))
      continue
    s,t=[],[]
    while v:
      s.append(v)
      v=(v+n-2)//n
    while w:
      t.append(w)
      w=(w+n-2)//n
    print(max(set(s)&set(t)))
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
if N == 1:
    anss = [min(v, w) for v, w in vws]
else:
    for v, w in vws:
        v, w = v-1, w-1
        while v != w:
            if v > w:
                v = (v-1)//N
            else:
                w = (w-1)//N
        anss.append(v + 1)

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
import sys
N, Q = map(int, input().split())
query = []
for i in range(Q):
    v, w = map(int, input().split())
    if v < w:
        v, w = w, v
    query.append((v - 1, w - 1))


def f(v, w):
    L = set()
    L.add(0)
    while w != 0:
        L.add(w)
        w = (w - 1) // N
    while v != 0:
        if v in L:
            return v + 1
        v = (v - 1) // N
    return 1

if N==1:
    for v, w in query:
        print(w+1)
    sys.exit()
for v, w in query:
    print(f(v, w))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))

Submission status: Accepted

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

if n == 1:
    def solve(v, w):
        return min(v, w)
else:
    def solve(v, w):
        while v != w:
            if v > w:
                v, w = w, v
            w = (w + n - 2) // n
        return v

print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))

Submission status: Accepted

Solution code:
from bisect import *
N, Q = map(int, input().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, input().split())
        print(v)
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, input().split())
        for i in range(bisect(B, v), bisect(B, w)):
            w = (w + (N - 2)) // N
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        print(v)

Submission status: Accepted

Solution code:
from bisect import *
from sys import stdin, stdout
readline = stdin.readline
N, Q = map(int, readline().split())
ans = []
if N == 1:
    for q in range(Q):
        v, w = map(int, readline().split())
        ans.append(str(v))
else:
    c = 1
    B = [1]
    while c < 10**9:
        B.append(c+1)
        c = c*N + 1
    for q in range(Q):
        v, w = map(int, readline().split())
        lv = bisect(B, v)
        lw = bisect(B, w)
        if lv < lw:
            w = (w + (B[lw-lv]-1)*(N-2)) // N**(lw-lv)
        while v != w:
            v = (v + (N - 2)) // N
            w = (w + (N - 2)) // N
        ans.append(str(v))
stdout.write("\n".join(ans))
stdout.write("\n")

Submission status: Runtime Error

Solution code:
import sys
import math
input=sys.stdin.readline
n,q=map(int,input().split())
for i in range(q):
    u,v=map(int,input().split())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            u=(u-1)//(n**(max(1,math.floor(math.log(n,u/(1.0*v))-1))))
        else:
            v=(v-1)//(n**(max(1,math.floor(math.log(n,v/(1.0*v))-1))))
    print(u+1)

Submission status: Runtime Error

Solution code:
def main():
    n,m=map(int,input().split())
    if n==1:
        for a,b in ab:
            print(min(a,b))
    ab=[list(map(int,input().split())) for _ in [0]*m]
    for a,b in ab:
        while a!=b:
            a,b=min(a,b),max(a,b)
            b=(b+n-2)//n
        print(a)
    
main()

Submission status: Runtime Error

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*n]
    for a,b in ab:
        while a!=b:
            a,b=min(a,b),max(a,b)
            b=(b+1)//3
        print(a)
    
    
main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

def query(tree, a, b):
    idxa = bisect_left(tree, a)
    idxb = bisect_left(tree, b)
    while a != b:
        cond1 = idxa >= idxb
        cond2 = idxa <= idxb
        if cond1:
            a = (a - tree[idxa-1]-1)//3 + tree[idxa-2]+1
            idxa -= 1
        if cond2:
            b = (b - tree[idxb-1]-1)//3 + tree[idxb-2]+1
            idxb -= 1
    return a

def main():
    N, Q = map(int, input().split())
    tree = [0]
    s = 0
    i = 1
    while s <= N:
        s += i
        tree.append(s)
        i *= 3
    print(tree)
    for _ in range(Q):
        v, w = map(int, input().split())
        print(query(tree, v, w))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect
n, q = [ int(v) for v in input().split() ]

tree_list = [0] + [ (n**(i+1)-1) // (n-1) for i in range(100) if (n**(i+1)-1) // (n-1) <= 10**9 ]

def upward(a):
    d = bisect.bisect_left(tree_list,a) - 1
    outlist = []
    for i in range(d+1):
        outlist.append(a)
        if i < d:
            a -= tree_list[d-i] + 1
            a //= n
            a += tree_list[d-i-1] + 1
    return d, outlist

def lca(a,b):
    da, a_list = upward(a)
    db, b_list = upward(b)

    if da < db:
        da, db = db, da
        a_list, b_list = b_list, a_list
    s = da - db
    ans = None
    for i in range(db+1):
        if a_list[s+i] == b_list[i]:
            ans = a_list[s+i]
            break
    return ans



for i in range(q):
    v, w = [ int(v) for v in input().split() ]
    print(lca(v,w))

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
if n==1:
    for i in range(q):
        v,w=map(int,input().split())
        print(min(v,w))
for i in range(q):
    v,w=map(int,input().split())
    while v!=w:
        if v>w:
            v=(v+n-2)//n
        else:
            w=(w+n-2)//n
    print(v)

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
for i in range(q):
  a,b = map(int,input().split())
  #include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<(n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,q;cin>>n>>q;
  for(int i=0;i<q;i++){
    ll a,b;cin>>a>>b;
    if(n==1)cout<<min(a,b)<<endl;
    else{
      vi hog;
      while(a>=1){
	hog.pb(a);
	a=(a+(n-2))/n;
      }
      bool fl=false;
      while(b>=1){
	if(fl)break;
	for(auto nu:hog){
	  //cout<<b<<" "<<nu<<endl;
	  if(b==nu){
	    cout<<b<<endl;
	    fl=true;
	    break;
	  }
	}
	b=(b+(n-2))/n;
      }
    }
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
from bisect import bisect
from itertools import accumulate


def solve(v, w):
    vl = bisect(table, v)
    wl = bisect(table, w)
    if vl > wl:
        for i in range(vl - wl):
            v = (v + m) // n
    elif wl < vl:
        for i in range(wl - vl):
            w = (w + m) // n
    while v != w:
        if v > w:
            v, w = w, v
        w = (w + m) // n
    return v


n, q = map(int, input().split())
m = n - 2
table, k = [], 1
while True:
    table.append(k)
    k *= n
    if k > 1e9:
        break
table = accumulate(table)

print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))