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: Wrong Answer

Solution code:
#evergrowing tree

N,Q=map(int,input().split())
def find_par(x):
    par=[x,1]
    while x!=0:
        x+=1
        u,v=divmod(x,N)
        par.append(u)
        x=u
    return par
for i in range(Q):
    v,w=map(int,input().split())
    a=find_par(v)
    a.sort(reverse=True)
    b=set(find_par(w))
    point=1
    for node in a:
        if node in b:
            point=node
            break
    print(node)

Submission status: Wrong Answer

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 and u!=0 and v!=0:
        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*u))-1))))
    if u==0 or v==0:
        print(1)
    else:
        print(u+1)

Submission status: Wrong Answer

Solution code:
def main():
    n,m=map(int,input().split())
    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+1)//n
        print(a)
    
    
main()

Submission status: Wrong Answer

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 and idxa >= 2:
            a = (a - tree[idxa-1]-1)//3 + tree[idxa-2]+1
            idxa -= 1
        if cond2 and idxb >= 2:
            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

    for _ in range(Q):
        v, w = map(int, input().split())
        print(query(tree, v, w))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def query(tree, a, b):
    while a != b:
        idxa = bisect_left(tree, a)
        idxb = bisect_left(tree, b)
        if idxa >= idxb:
            a = (a - tree[idxa-1]-1)//3 + tree[idxa-2]+1
        if idxa <= idxb:
            b = (b - tree[idxb-1]-1)//3 + tree[idxb-2]+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
    for _ in range(Q):
        v, w = map(int, input().split())
        print(query(tree, v, w))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 + 1) // n
        print(i)

Submission status: Wrong Answer

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 == i:
        print(min(i, j))
    else:
        while i != j:
            if i < j:
                i, j = j, i
            i = (i + 1) // n
        print(i)

Submission status: Wrong Answer

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):
    while i != j:
        if i < j:
            i, j = j, i
        i = (i + 1) // 3
    print(i)

Submission status: Wrong Answer

Solution code:
import math
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(max(min(v, w) - 1, 1))
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: Wrong Answer

Solution code:
n,q=map(int,input().split())
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: Wrong Answer

Solution code:
n,q=map(int,input().split())
for _ in range(q):
    v,w=map(int,input().split())
    if n == 1:
        print(min(v,w))
        continue
    
    while(v is not w):
        if v < w:
            w = (w+n-2)//n
        else:
            v = (v+n-2)//n
    print(v)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
for _ in range(q):
    v,w=map(int,input().split())
    if n == 1:
        print(min(v,w))
        continue
    
    while(v is not w):
        if v < w:
            w = (w+n-1)//n
        else:
            v = (v+n-1)//n
    print(v)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
for _ in range(q):
    v,w=map(int,input().split())
    while(v is not w):
        if v < w:
            w = (w+1)//3
        else:
            v = (v+1)//3
    print(v)

Submission status: Wrong Answer

Solution code:
def pre(x, N):
    return (x + N - 2) // N


N, Q = map(int, input().split())
cache = {}
for i in range(Q):
    v, w = map(int, input().split())
    if (v, w) in cache:
        print(cache[(v, w)])
    inp_v = v
    inp_w = w
    if N == 1:
        print(min(v, w))
        continue
    while v != w:
        if v < w:
            w = pre(w, N)
        else:
            v = pre(v, N)
    cache[(inp_v, inp_w)] = v
    print(v)

Submission status: Wrong Answer

Solution code:
def pre(x):
    return (x + 1) // 3


N, Q = map(int, input().split())
for i in range(Q):
    v, w = map(int, input().split())
    while v != w:
        if v < w:
            w = pre(w)
        else:
            v = pre(v)
    print(v)

Submission status: Wrong Answer

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 % 3 == 0):
      return x // 3
   elif (x % 3 == 1):
      return (x - 1) // 3
   else:
      return (x + 1) // 3
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: Wrong Answer

Solution code:
N, Q = map(int, input().split())
for q in range(Q):
    v, w = map(int, input().split())
    while v*N <= w - 2 + N:
        w = (w - 2 + N)//N
    while v != w:
        v = (v - 2 + N)//N
        w = (w - 2 + N)//N
    print(v)

Submission status: Wrong Answer

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(rank**N + idx + 1)

Submission status: Wrong Answer

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())
  if a > b: a,b = b,a
  p1,p2 = pos(a),pos(b)
  while p2[0] > p1[0]:
    p2 = parent(p2)
  while p1 != p2:
    p1,p2 = parent(p1),parent(p2)
  rank,idx = p1
  print(rank**N + idx + 1)

Submission status: Wrong Answer

Solution code:
import bisect
N,Q = map(int,raw_input().split())
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())
  if a > b: a,b = b,a
  p1,p2 = pos(a),pos(b)
  while p2[0] > p1[0]:
    p2 = parent(p2)
  while p1 != p2:
    p1,p2 = parent(p1),parent(p2)
  rank,idx = p1
  print(rank**N + idx + 1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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())

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()

Submission status: Time Limit Exceeded

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())
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

Submission status: Time Limit Exceeded

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 = []
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: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
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))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
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=path(w)
    data2.sort(reverse=True)
    for num in data2:
        if num in data1:
            print(num)
            break

Submission status: Time Limit Exceeded

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())
    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: Time Limit Exceeded

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())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            if (u-1)//n>v:
                u=(u-1)//(n*n)
            else:
                u=(u-1)//n
        else:
            if (v-1)//n>v:
                v=(v-1)//(n*n)
            else:
                v=(v-1)//n
    print(u+1)

Submission status: Time Limit Exceeded

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())
    u-=1
    v-=1
    while u!=v:
        if u>v:
            u=(u-1)//n
        else:
            v=(v-1)//n
    print(u+1)

Submission status: Time Limit Exceeded

Solution code:
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
        else:
            v=(v-1)//n
    print(u+1)

Submission status: Time Limit Exceeded

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:
            a,b=min(a,b),max(a,b)
            b=(b+n-2)//n
        print(a)
    
main()

Submission status: Time Limit Exceeded

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()]
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: Time Limit Exceeded

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()]
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
    ans += str(v+1) + "\n"
print(ans)

Submission status: Time Limit Exceeded

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

n, q = [int(item) for item in input().split()]
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: Time Limit Exceeded

Solution code:
import math
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: 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:
    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: 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:
    for i in range(q):
        v,w=map(int,input().split())
        while v!=w:
            while v>w:
                v=(v+n-2)//n
            while w>v:
                w=(w+n-2)//n
        print(v)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
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: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
for i in range(q):
    v,w=map(int,input().split())
    c=[1]
    while v!=1:
        c.append(v)
        v=(v+n-2)//n
    while w not in c:
        w=(w+n-2)//n
    print(w)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
if n == 1:
  for _ in range(q):
    print(min(map(int, input().split())))
else:
  for _ 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: Time Limit Exceeded

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

N,Q = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(Q)]

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

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

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
VW = [[int(x) for x in input().split()] for _ in range(Q)]

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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:
    v,w=sorted((v,w))
    w=(w+n-2)//n
  print(v)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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,v,w=[],[],[v],[w]
    for i in v:
      s.append(i)
      a=(i+n-2)//n
      if a:v.append(a)
    for j in w:
      t.append(j)
      b=(j+n-2)//n
      if b:w.append(b)
    print(max(set(s)&set(t)))
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
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=set(),set()
  while v:
    s|={v}
    v=(v+n-2)//n
  while w:
    t|={w}
    w=(w+n-2)//n
  print(max(s&t))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())

    anss = []
    for _ in range(Q):
        v, w = map(int, input().split())
        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)))

solve()

Submission status: Time Limit Exceeded

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

anss = []
for v, w in vws:
    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: Time Limit Exceeded

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

anss = []
for v, w in vws:
    parVs, parWs = set(), set()
    while v >= 0:
        parVs.add(v)
        v = (v-1)//N
    while w >= 0:
        parWs.add(w)
        w = (w-1)//N
    anss.append(max(parVs & parWs) + 1)

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
if N == 1:
    for _ in range(Q):
        v, w = map(int, input().split())
        print(min(v, w))
else:
    L = [1]
    aa = 1
    def ch(k):
        return (k-2)//N+1
    
    def chh(a, b):
        if a == b:
            return a
        
        if a > b:
            a, b = b, a
        
        return chh(a, ch(b))
        
    for _ in range(Q):
        v, w = map(int, input().split())
        print(chh(v, w))

Submission status: Time Limit Exceeded

Solution code:
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):
    a=w
    b=v
    s=0
    t=0
    while w != 0:
        w = (w - 1) // N
        s+=1
    while v != 0:
        v = (v - 1) // N
        t+=1
    u=t-s
    while u>0:
        b = (b - 1) // N        
        u-=1
    while a!=b:
        b = (b - 1) // N            
        a = (a - 1) // N  
    return a+1
for v, w in query:
    print(f(v, w))

Submission status: Time Limit Exceeded

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


for v, w in query:
    print(f(v, w))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
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
for i in range(Q):
    v, w = map(int, input().split())
    v,w=v-1,w-1
    if v > w:
        v, w = w, v
    print(f(v, w))

Submission status: Time Limit Exceeded

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


for v, w in query:
    print(f(v, w))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,q = (int(i) for i in input().split())
x,num = [1],1
while x[-1]<=10**9:
	x.append(n**num+x[-1])
	num += 1
from bisect import bisect_left
def par(c):
	cp = bisect_left(x,c)
	if cp==0: return 0
	elif cp==1: return 1
	else: return x[cp-2]+(c-1-x[cp-1])//n+1
for _ in range(q):
	v,w = (int(i) for i in input().split())
	vp,wp = bisect_left(x,v),bisect_left(x,w)
	while vp!=wp: w,wp = par(w),wp-1
	while v!=w: v,w = par(v),par(w)
	print(v)

Submission status: Time Limit Exceeded

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

src = [tuple(map(int,input().split())) for i in range(Q)]
for a,b in src:
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    print(a)

Submission status: Time Limit Exceeded

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

for i in range(Q):
    a,b = map(int,input().split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    print(a)

Submission status: Time Limit Exceeded

Solution code:
def pre(x, N):
    return (x + N - 2) // N


N, Q = map(int, input().split())
cache = {}
for i in range(Q):
    v, w = map(int, input().split())
    if N == 1:
        print(min(v, w))
        continue
    if (v, w) in cache:
        print(cache[(v, w)])
        continue
    adds = []
    while v != w:
        adds.append((v, w))
        if v < w:
            w = pre(w, N)
        else:
            v = pre(v, N)
    for add in adds:
        cache[(min(add), max(add))] = v
    print(v)

Submission status: Time Limit Exceeded

Solution code:
def pre(x, N):
    return (x + N - 2) // N


N, Q = map(int, input().split())
cache = {}
for i in range(Q):
    v, w = map(int, input().split())
    if (v, w) in cache:
        print(cache[(v, w)])
        continue
    inp_v = v
    inp_w = w
    if N == 1:
        print(min(v, w))
        continue
    while v != w:
        if v < w:
            w = pre(w, N)
        else:
            v = pre(v, N)
    cache[(inp_v, inp_w)] = v
    print(v)

Submission status: Time Limit Exceeded

Solution code:
def pre(x, N):
    return (x + N - 2) // N


N, Q = map(int, input().split())
for i in range(Q):
    v, w = map(int, input().split())
    if N == 1:
        print(min(v, w))
        continue
    while v != w:
        if v < w:
            w = pre(w, N)
        else:
            v = pre(v, N)
    print(v)

Submission status: Time Limit Exceeded

Solution code:
def pre(x, N):
    return (x + N - 2) // N


N, Q = map(int, input().split())
for i in range(Q):
    v, w = map(int, input().split())
    while v != w:
        if v < w:
            w = pre(w, N)
        else:
            v = pre(v, N)
    print(v)

Submission status: Time Limit Exceeded

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 = list(accumulate(table))

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

Submission status: Time Limit Exceeded

Solution code:
def solve(v, w):
    while v != w:
        if v > w:
            v, w = w, v
        w = (w + n - 2) // n
    return v


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