Background

This problem is an enhanced version of Pairing Pairs. The constraints and the input/output method are different.

Problem Description

You are given some pairs $(u_i, v_i)$ (it is guaranteed that $0 \le u_i < v_i < n$, and all pairs are distinct). For each $i$, find a $j$ such that the four numbers $u_i, v_i, u_j, v_j$ are all pairwise distinct, or report that it does not exist.

To speed up input and output, this problem uses an interactive grader. Please note the difference between this problem and the contest version: in this problem, both input and output indices start from $0$.

You need to implement a function int* find_pairs(int n,int m,int u[],int v[]), where $n, m, u, v$ are as described above.

The return value is an array (call it ans). Then ans[i] means the $j$ you found for $i$. If such a $j$ does not exist, then ans[i] = -1, not $0$.

Since the return value is a pointer, please ensure that the returned array is allocated on the heap. For details, you may refer to this blog post.

Input Format

The following input/output format is the input/output format of sample_interactive_lib.cpp. You do not need to read or write any data, and you should not even implement the main function.

The first line contains two positive integers $n, m$, representing the range of numbers in the pairs and the number of pairs.

Then there are $m$ lines. The $i$-th line contains two positive integers $u_i, v_i$, representing the $i$-th pair.

Output Format

Output one line with $m$ integers. The $i$-th integer is the $j$ you found for $i$. If the corresponding $j$ does not exist, output $-1$.

If there are multiple valid $j$, output any one of them.

7 5
0 2
2 3
0 3
2 5
3 6

4 -1 3 4 0

Hint

[Sample Explanation]

According to the program, the sample interactive library will call find_pairs(7,5,{0,2,0,2,3},{2,3,3,5,6}). Then, if the array you return is {4,-1,3,4,0}, you will get the sample output. This sample output is valid.

[Constraints]

For all testdata, it is guaranteed that $1 \le n, m \le 10^7$.

The time for std is $324$ ms, and the memory is $267.87$ MB.

Translated by ChatGPT 5