#!/usr/bin/env python3
import sys
import heapq


def solve(N: int, Q: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    MAX_RATE = -11**9
    en = [[MAX_RATE]*N for _ in range(2*10**5)]
    enji = [-1]*N
    byodo = [0] * len(en)

    for i, (ai, bi) in enumerate(zip(A,B)):
        en[bi-1][i] = ai
        enji[i] = bi
        byodo[bi-1] = max(byodo[bi-1], ai)

    byodo = [i if i!=0 else -MAX_RATE for i in byodo ]

    for ci, di in zip(C,D):

        bef_en = enji[ci-1]
        enji[ci-1] = di

        r = en[bef_en-1][ci-1]
        en[bef_en-1][ci-1] = MAX_RATE        
        en[di-1][ci-1] = r

        max_bef = max(en[bef_en-1])
        max_di = max(en[di-1])

        if max_bef != byodo[bef_en-1]:
            if max_bef !=MAX_RATE:
                byodo[bef_en-1] = max_bef
            else:
                byodo[bef_en-1] = -MAX_RATE

        if max_di != byodo[di-1]:
            if max_di !=MAX_RATE:
                byodo[di-1] = max_di
            else:
                byodo[di-1] = -MAX_RATE

        
        print(min(byodo))


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (Q)  # type: "List[int]"
    D = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, Q, A, B, C, D)

if __name__ == '__main__':
    main()
