n, m = map(int, input().split())
hands = [tuple(map(int, input().split())) for _ in range(n)]
_cuts = [tuple(map(int, input().split())) for _ in range(m)]
edges = [[] for u in range(n + 1)]
edge_cnt = [{} for u in range(n + 1)]

for u, (l, r) in enumerate(hands, 1):
    for v in [l, r]:
        if v == -1:
            continue
        _u, _v = min(u, v), max(u, v)
        edge_cnt[_u][_v] = edge_cnt[_u].get(_v, 0) + 1

cuts = [
    (min(u, v), max(u, v))
    for m, lr in _cuts
    if (u := m) and (v := hands[m - 1][lr - 1])
]

for u, v in cuts:
    edge_cnt[u][v] -= 1

for u in range(1, n + 1):
    for v in edge_cnt[u]:
        if edge_cnt[u][v] > 0:
            edges[u].append(v)

res, rank = [-1]*(n + 1), [0]*(n + 1)
p = [i for i in range(n + 1)]
c = [set() for i in range(n + 1)]

def get(x):
    stk = []
    while x != p[x]:
        stk.append(x)
        x = p[x]
    for i in stk:
        c[p[i]].remove(i)
        c[x].add(i)
        p[i] = x
    return x

def union(u, v):
    pu, pv = get(u), get(v)
    if pu == pv:
        return
    if rank[pu] == rank[pv]:
        rank[pu] += 1
    if rank[pu] < rank[pv]:
        pu, pv = pv, pu
    p[pv] = pu
    c[pu].add(pv)

def set(x, idx):
    stk = [x]
    while stk:
        cur = stk.pop()
        res[cur] = idx
        stk.extend(c[cur])

for u in range(1, n + 1):
    for v in edges[u]:
        union(u, v)

for idx, (u, v) in list(enumerate(cuts))[::-1]:
    p1, pu, pv = get(1), get(u), get(v)
    if pu == pv == p1:
        continue
    if p1 in [pu, pv]:
        set(pu, idx) if pu != p1 else set(pv, idx)
    union(u, v)

print("\n".join(map(str, res[1:])))