@staticmethod
def e():
    (n, q) = map(int, sys.stdin.readline().split())
    queue = []
    m = (2 * (10 ** 5))
    infants = [[] for _ in range(m)]
    highest_rate = ([None] * m)
    where = ([None] * n)
    rate = ([None] * n)

    def entry(i, k):
        where[i] = k
        while infants[k]:
            (r, j) = heappop(infants[k])
            if ((where[j] != k) or (j == i)):
                continue
            if (rate[i] >= (- r)):
                highest_rate[k] = rate[i]
                heappush(queue, (rate[i], k, i))
            heappush(infants[k], (r, j))
            break
        else:
            highest_rate[k] = rate[i]
            heappush(queue, (rate[i], k, i))
        heappush(infants[k], ((- rate[i]), i))

    def transfer(i, k):
        now = where[i]
        while infants[now]:
            (r, j) = heappop(infants[now])
            if ((where[j] != now) or (j == i)):
                continue
            if (highest_rate[now] != (- r)):
                highest_rate[now] = (- r)
                heappush(queue, ((- r), now, j))
            heappush(infants[now], (r, j))
            break
        else:
            highest_rate[now] = None
        entry(i, k)

    def inquire():
        while True:
            (r, k, i) = heappop(queue)
            if ((where[i] != k) or (r != highest_rate[k])):
                continue
            heappush(queue, (r, k, i))
            return r
    for i in range(n):
        (a, b) = map(int, sys.stdin.readline().split())
        rate[i] = a
        entry(i, (b - 1))
    for _ in range(q):
        (c, d) = map(int, sys.stdin.readline().split())
        transfer((c - 1), (d - 1))
        print(inquire())
@staticmethod
def e():
    (n, q) = map(int, sys.stdin.readline().split())
    queue = []
    m = (2 * (10 ** 5))
    infants = [[] for _ in range(m)]
    highest_rate = ([None] * m)
    where = ([None] * n)
    rate = ([None] * n)

    def entry(i, k):
        where[i] = k
        while infants[k]:
            (r, j) = heappop(infants[k])
            if ((where[j] != k) or (j == i)):
                continue
            if (rate[i] >= (- r)):
                highest_rate[k] = rate[i]
                heappush(queue, (rate[i], k, i))
            heappush(infants[k], (r, j))
            break
        else:
            highest_rate[k] = rate[i]
            heappush(queue, (rate[i], k, i))
        heappush(infants[k], ((- rate[i]), i))

    def transfer(i, k):
        now = where[i]
        while infants[now]:
            (r, j) = heappop(infants[now])
            if ((where[j] != now) or (j == i)):
                continue
            if (highest_rate[now] != (- r)):
                highest_rate[now] = (- r)
                heappush(queue, ((- r), now, j))
            heappush(infants[now], (r, j))
            break
        else:
            highest_rate[now] = None
        entry(i, k)

    def inquire():
        while True:
            (r, k, i) = heappop(queue)
            if ((where[i] != k) or (r != highest_rate[k])):
                continue
            heappush(queue, (r, k, i))
            return r
    for i in range(n):
        (a, b) = map(int, sys.stdin.readline().split())
        rate[i] = a
        entry(i, (b - 1))
    for _ in range(q):
        (c, d) = map(int, sys.stdin.readline().split())
        transfer((c - 1), (d - 1))
        print(inquire())