Independent Edge Set and Certificate

Let $G$ be a simple undirected graph. Two vertices of $G$ are adjacent if an edge connects them, and two edges of $G$ are adjacent if they share a vertex. In the graph of Figure 1(a), vertices $3$ and $4$ are adjacent because the edge $(3,4)$ connects them. The edges $(3,4)$ and $(3,5)$ are adjacent because they share vertex $3$.

A subset of the vertices of $G$ is an independent vertex set if no two of its vertices are adjacent. A subset of the edges of $G$ is an independent edge set if no two of its edges are adjacent. The size of a largest independent vertex set is the vertex independence number, written $\alpha(G)$. In the same way, the size of a largest independent edge set is the edge independence number, written $\nu(G)$.

Figure 1. Two graphs $G_1$ and $G_2$. (a) The graph $G_1$, where $\alpha(G_1) = 4$ and $\nu(G_1) = 4$. (b) The graph $G_2$, where $\alpha(G_2) = 6$ and $\nu(G_2) = 3$.

The independent edge set problem asks for a largest independent edge set of a graph. It has been studied for a long time, and several algorithms run in time polynomial in the size of the graph. Still, when a program reads an input $X$ and prints an answer $Y$, the user has no way to tell whether $Y$ is correct or has been broken by a bug. A certifying algorithm prints, together with its answer, a certificate $Z$ for that answer. The user inspects $Z$ by hand or feeds it to a checker program, and then either accepts the answer as correct or discards it as buggy.

Consider what makes a good certificate for the independent edge set problem on a bipartite graph. A graph is bipartite if its vertex set splits into two disjoint sets $U$ and $V$ so that every edge joins a vertex of $U$ to a vertex of $V$. Both graphs of Figure 1 are bipartite, with the orange vertices forming one side and the blue vertices the other. König's theorem says that every bipartite graph $G$ on $n$ vertices satisfies $\nu(G) + \alpha(G) = n$. A maximum independent vertex set is therefore a good certificate. Once an independent edge set of size $k$ and an independent vertex set of size $n - k$ have been found in a bipartite graph on $n$ vertices, $\nu(G) = k$ and $\alpha(G) = n - k$ follow, so both sets are as large as possible.

You are given a bipartite graph $G$. Find and print a maximum independent edge set $Y$ together with a maximum independent vertex set $Z$, which is the certificate. The vertices are numbered from $1$ to $n$. A checker confirms that no two edges of $Y$ are adjacent, confirms that no two vertices of $Z$ are adjacent, and accepts the answer when $|Y| + |Z| = n$.

The first line contains the number of vertices $n$ and the number of edges $m$, separated by a space. ($1 \le n \le 1000$, $1 \le m \le 50000$)

Each of the next $m$ lines contains one edge, given as the numbers $u$ and $v$ of the two vertices it joins, separated by a space. ($1 \le u, v \le n$, $u \neq v$)

The given graph is a simple bipartite graph and is not necessarily connected. No edge is given twice.

On the first line, print the size $k$ of a maximum independent edge set.

On each of the next $k$ lines, print one edge of that set. Print the two vertex numbers of an edge in increasing order. Order the lines by the first number, and by the second number when the first numbers are equal. If the graph has several maximum independent edge sets, print the one whose sorted edge list is lexicographically smallest.

On the next line, print the size $k'$ of the certificate, and on the line after it print the vertices of the certificate in ascending order, separated by single spaces. If the graph has several maximum independent vertex sets, print the one whose ascending vertex list is lexicographically smallest.

Exactly one output satisfies both rules.