Graph Transformation Sequence

We are given two undirected simple graphs with the same vertex set: an initial graph $S$ and a target graph $T$. The target graph is assumed to be constructed by the following transformation procedure from $S$:

1. Initialize an empty graph $T$ on $n$ vertices (i.e. no edges).
2. While there are at least two vertices in $S$, choose two vertices $u$ and $v$ from $S$ that have equal degree (i.e. $$deg_S(u)=deg_S(v)$$). Then, add the edge $(u,v)$ to $T$ and remove vertex $u$ (together with all edges incident to $u$) from $S$.
3. When only one vertex remains in $S$, the constructed graph $T$ is obtained.

Moreover, one may iterate this procedure: starting from $S$, we perform one transformation $S\to T_1$, from which a further transformation $T_1\to T_2$ (and so on) may be done. In this problem, you are given $S$ and $T$ (both on $n$ vertices) and your task is to find at least one sequence of transformations (with at least $1$ and at most $3$ transformation steps) such that

where in each transformation the chosen edges (the pairs $(u,v)$ selected in that procedure) exactly form the constructed tree. The input is guaranteed to have a solution. If there are multiple valid answers, output any one of them.

inputFormat

The first line contains a single integer $n$ (the number of vertices). Then follows the description of the graph $S$: • An integer $m_1$ representing the number of edges in $S$, followed by $m_1$ lines each containing two integers $u$ and $v$ (1-based) that denote an edge between vertices $u$ and $v$. Next is the description of the graph $T$: • An integer $m_2$ representing the number of edges in $T$, followed by $m_2$ lines each containing two integers $u$ and $v$ that denote an edge between vertices $u$ and $v$.

outputFormat

Output a valid transformation sequence which consists of exactly $k$ transformation procedures (with $1\le k\le 3$). For each transformation procedure, output an integer $r$ on a separate line (which should equal $n-1$, the number of operations in that procedure), followed by $r$ lines each containing two integers $u$ and $v$ representing the pair chosen in that operation. The overall first line of the output should be the integer $k$. (Note: In our solutions we use $k=1$, i.e. a single transformation.)

sample

3
3
1 2
1 3
2 3
2
1 2
2 3

1
2
1 2
3 2