P10248 Pairing Pairs (Enhanced Version).

This problem is an enhanced version of [Pairing Pairs](https://www.luogu.com.cn/problem/P10247). The constraints and the input/output method are different.

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](https://www.luogu.com.cn/article/sxyv0830).**

**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 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.

[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