409372: GYM103492 J Bigraph Extension

There are $$$2n$$$ vertices ($$$n$$$ is even), $$$n$$$ of which belong to set $$$A$$$, and the rest $$$n$$$ belong to set $$$B$$$. Initially, there are $$$m$$$ undirected edges in the graph, where the two vertices of each edge are not in the same set. In addition, there is no common vertex between any two edges.

You are required to do the following operation multiple times:

• Choose a vertex from set $$$A$$$ and another from set $$$B$$$ on the condition that these two vertices are not directly connected by an edge. Then add an edge to connect the two vertices.

After that, when you choose any vertex in set $$$A$$$ and any vertex in set $$$B$$$, the following conditions must be satisfied:

• The two vertices are connected, which means there exists a path that leads from one vertex to the other.
• The number of edges in the longest simple path between the two vertices is strictly greater than $$$n$$$. (In a simple path, each vertex is visited no more than once.)

Please minimize the number of edges you add.

The first line contains a single integer $$$T$$$ $$$(1\le T \le 10^{3})$$$, representing the number of test cases.

For each test case, the first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^{3}, 0 \leq m \leq n$$$, $$$n$$$ is even), representing the number of vertices in one set and the number of initial edges.

In the following $$$m$$$ lines, each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n $$$), indicating an edge between the $$$u$$$-th vertex in set $$$A$$$ and the $$$v$$$-th vertex in set $$$B$$$. It's guaranteed that there is no common vertex between any two edges.

For each test case, if there is no solution, print -1 in a single line.

Otherwise, the first line of the output contains an integer $$$k$$$, indicating the minimum number of edges you add. In the following $$$k$$$ lines, the $$$i$$$-th line contains two integers $$$c_i$$$ and $$$d_i$$$ ($$$1 \leq c_i,d_i \leq n$$$), indicating an edge you add between the $$$c_i$$$-th vertex in set $$$A$$$ and the $$$d_i$$$-th vertex in set $$$B$$$.

As there may be multiple valid solutions, you need to output the answer which makes the sequence $$$c_1,d_1,c_2,d_2,\ldots ,c_k,d_k$$$ have the smallest lexicographical order. Sequence $$$p_1, p_2, \dots, p_n$$$ is lexicographically smaller than $$$q_1, q_2, \dots, q_n$$$ if $$$p_i < q_i$$$ where $$$i$$$ is the minimum index satisfying $$$p_i \neq q_i$$$.

1
2 1
1 2

3
1 1
2 1
2 2

For the sample, we can prove that the minimal $$$k$$$ is $$$3$$$. Here, we use $$$A_i$$$ to indicate the $$$i$$$-th vertex in set $$$A$$$ and $$$B_i$$$ to indicate the $$$i$$$-th vertex in set $$$B$$$.

The longest path from $$$A_1$$$ to $$$B_1$$$ is $$$A_1\to B_2\to A_2\to B_1$$$.

The longest path from $$$A_2$$$ to $$$B_1$$$ is $$$A_2\to B_2\to A_1\to B_1$$$.

The longest path from $$$A_1$$$ to $$$B_2$$$ is $$$A_1\to B_1\to A_2\to B_2$$$.

The longest path from $$$A_2$$$ to $$$B_2$$$ is $$$A_2\to B_1\to A_1\to B_2$$$.

The answer $$$(1,1),(2,2),(2,1)$$$ is also valid, but it is not lexicographically smallest.