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




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

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



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

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




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

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


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

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


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