Background

PA 2024 2B

Problem Description

This problem is translated from PA 2024 Round 2 Alchemik Bajtazar.

Byteasar is a famous alchemist. To solve the problem of transmutation of materials, he has temporarily put aside his attempts to create the Philosopher’s Stone. More precisely, Byteasar wants to transform one molecule into another. The molecule he currently has consists of $n$ bytonium atoms (in Byteotia, bytonium is one of the most commonly used chemical elements, mainly used to produce food and contact lenses). The atoms are numbered from $1$ to $n$. There may be bonds between some pairs of atoms, but between any pair there is at most one bond. These molecules form a connected whole: starting from any atom, you can reach any other atom by following one or more bonds.

Byteasar has described the bonds in the molecule of $n$ atoms that he wants to obtain: for every pair of atoms, he knows whether he wants them to be connected by a bond in the end. The target molecule satisfies the same conditions: it is connected, and there is at most one bond between any pair of atoms. Unfortunately, Byteasar’s current molecule may differ from the target molecule. To fix this, he can use his alchemical powers. At any moment, he can perform one of the following two operations:

• Byteasar may choose two different atoms $a$ and $b$ that are not connected by a bond, and create a bond between them. Due to the high instability of bytonium, he can do this only if there currently exists an atom $c$ (different from $a$ and $b$) that is bonded to both $a$ and $b$.
• Byteasar may choose two different atoms $a$ and $b$ that are connected by a bond, and remove the bond between them. For similar reasons, he can do this only if there currently exists an atom $c$ (different from $a$ and $b$) that is bonded to both $a$ and $b$.

Byteasar does not want to spend too much time on the transformation. Write a program to help him transform his molecule into the target molecule using at most $200\,000$ operations.

Note: all atoms are pairwise different and distinguishable.

Input Format

The first line contains an integer $n\ (2\le n\le 30\,000)$, the number of atoms in Byteasar’s molecule and in the target molecule.

The second line contains an integer $m_s\ (n-1 \le m_s \le 50\, 000)$, the number of bonds in Byteasar’s current molecule.

The next $m_s$ lines each contain two integers. In the $i$-th of these lines, the integers $a_i$ and $b_i\ (1 \le a_i , b_i \le n, a_i \neq b_i)$ denote the numbers of atoms connected by a bond. It is guaranteed that Byteasar’s molecule is connected and that any pair of atoms is connected by at most one bond.

The next line contains an integer $m_d\ (n-1\le m_d\le 50\,000)$, the number of bonds in the target molecule.

The next $m_d$ lines describe these bonds in the same format as for the current molecule.

Output Format

The first line should contain the total number of operations $r$. You must ensure that $0\le r\le 200\,000$.

Each of the following lines should describe one operation. If in the $i$-th move you want to connect atoms $x_i$ and $y_i$, then the $i$-th line should start with +, followed by a space, and then the numbers $x_i$ and $y_i$ separated by a space. Conversely, if you want to remove the bond connecting atoms $x_i$ and $y_i$, then the line should start with -, and similarly output $x_i$ and $y_i$.

The output sequence of operations must satisfy the conditions given in the statement: when choosing atoms $x_i$ and $y_i$, there must exist another atom that is bonded to both of them. After performing all operations, the final molecule must be identical to the target molecule. That is, for every pair of atoms $i, j\ (1 \le i < j \le n)$, if atoms $i$ and $j$ are connected by a bond in the target molecule, then they must also be connected by a bond in the final state.

Note that you do not need to minimize the number of moves; you only need to perform at most $200\,000$ operations. It can be proven that it is always possible to achieve the transformation in no more than $200\,000$ operations.

4
3
1 2
3 4
3 2
4
1 4
1 2
2 3
3 4

3
+ 1 3
+ 1 4
- 3 1

Hint

Note that Byteasar cannot immediately connect the first atom to the fourth atom, because at that time there is no atom that is connected to both of them. By creating a temporary bond between the first and the third atom, Byteasar makes that atom a common neighbor of the third atom.

Translated by ChatGPT 5