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


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

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

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

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

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

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

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