Buggy python submission (verdict: Time Limit Exceeded):
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")


Fixed submission:
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")

Buggy python submission (verdict: Time Limit Exceeded):
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))


Fixed submission:
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")

Buggy python submission (verdict: Time Limit Exceeded):
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))


Fixed submission:
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")

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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")

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:
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")