题目背景

本题是 Pairing Pairs 的加强版，数据范围和输入输出方式都有区别。

题目描述

你有一些数对 $(u_i,v_i)$（保证 $0\le u_i<v_i<n$ 且数对两两不同），对于每个 $i$ 找一个 $j$ 使得 $u_i,v_i,u_j,v_j$ 四个数两两不同，或报告不存在。

为加速输入输出，本题采用 grader 交互。请注意本题和赛时题目的区别，本题输入和输出的下标均从 $0$ 开始。

你需要实现一个函数 int* find_pairs(int n,int m,int u[],int v[])，其中 $n,m,u,v$ 如题意所示。

返回值是一个数组（设为 ans），则 ans[i] 表示你对于 $i$ 找到的 $j$。若这样的 $j$ 不存在，则 ans[i]=-1，不是 $0$。

由于本题的返回值是一个指针，请保证返回的数组在堆空间中，具体可以参考这篇博客。

输入格式

以下输入输出格式均为 sample_interactive_lib.cpp 的输入输出格式。你不需要输入或输出任何数据，甚至不应该实现 main 函数。

输入的第一行有两个正整数 $n,m$ 表示数对中数字的范围和数对的个数。

之后 $m$ 行，其中的第 $i$ 行有两个正整数 $u_i,v_i$ 表示第 $i$ 个数对。

输出格式

输出一行 $m$ 个自然数，其中第 $i$ 个数表示你对这个 $i$ 找到的 $j$。若对应的 $j$ 不存在则输出 $-1$。

若符合题意的 $j$ 有多个，任意输出一个都可以通过本题。

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

4 -1 3 4 0

提示

【样例解释】

根据该程序，样例交互库将会调用 find_pairs(7,5,{0,2,0,2,3},{2,3,3,5,6})，然后如果你返回的数组是 {4,-1,3,4,0}，就会得到样例输出。这个样例输出是合法的。

【数据范围】

对于全体数据，保证 $1\le n,m\le 10^7$。

std 用时为 $324$ 毫秒，空间为 $267.87$ MB。