Find a Disjoint Pair

You are given m pairs \((u_i,v_i)\) satisfying \(1 \le u_i < v_i \le n\) with the guarantee that all pairs are distinct. For each pair \(i\) you need to find an index \(j\) (with \(j \neq i\)) such that the four numbers \(u_i, v_i, u_j, v_j\) are all distinct. If no such \(j\) exists for a particular \(i\), output \(-1\) for that \(i\).

Input Format: The first line contains two integers \(n\) and \(m\). Each of the next \(m\) lines contains two integers representing \(u_i\) and \(v_i\) respectively.

Output Format: Output \(m\) lines. For each \(i\) from 1 to \(m\), output a single integer: a valid index \(j\) (1-indexed) whose corresponding pair is disjoint from pair \(i\), or \(-1\) if no such pair exists.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space. Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) satisfying \(1 \le u_i < v_i \le n\). All \(m\) pairs are distinct.

outputFormat

Output \(m\) lines. The \(i\)th line should contain a single integer: the index \(j\) (1-indexed) such that \(u_i, v_i, u_j, v_j\) are all pairwise distinct, or \(-1\) if such a pair does not exist.

sample

6 3
1 2
3 4
5 6

2
1
1