Distinct Pairs Selection

You are given m unique number pairs ((u_i, v_i)) satisfying (0 \le u_i < v_i < n). For each index (i) (0-indexed), you need to choose an index (j) (also 0-indexed) such that the four numbers (u_i, v_i, u_j, v_j) are pairwise distinct. If no such (j) exists, output (-1) for that index.

In order to speed up input and output, this problem uses a grader interaction model. Note that the array indices in both input and output start from (0).

You need to implement a function with the following signature:

(int* find_pairs(int n, int m, int u[], int v[]))

The function should return a pointer to an array (allocated on the heap) of length (m), where the (i)th element is the selected index (j) for the (i)th pair, or (-1) if no valid (j) exists. Please refer to this blog for details about returning pointers to heap-allocated memory.

inputFormat

Input is given via standard input. The first line contains two integers (n) and (m). The following (m) lines each contain two integers (u_i) and (v_i) (0-indexed) satisfying (0 \le u_i < v_i < n). All pairs ((u_i, v_i)) are unique.

outputFormat

Output a single line containing (m) integers separated by spaces. The (i)th integer is the selected index (j) for the (i)th input pair, or (-1) if no valid pair exists.

sample

5 3
0 1
1 2
3 4

2 2 0