题目背景

PA 2024 2B

题目描述

题目译自 PA 2024 Runda 2 Alchemik Bajtazar

Byteasar 是一位著名的炼金术士，为了解决材料的嬗变问题，他暂时放下了制造贤者石的尝试。具体来说，Byteasar 想把一种分子转化成另一种。Byteasar 所拥有的分子由 $n$ 个 bytonium 原子组成（在 Byteotia，bytonium 是最常用的化学元素之一，主要用于生产食品和隐形眼镜），这些原子从 $1$ 到 $n$ 编号。某些原子对之间可能存在键，但每对原子之间最多只有一个键。这些分子形成了一个连贯的整体——从每个原子出发，通过一个或多个键就可以到达其他任何原子。

Byteasar 描述了他希望得到的 $n$ 个原子的分子中的键——对于每一对原子，他都知道是否希望它们最终由键连接。目标分子满足同样的条件——它形成一个连贯的整体，每对原子最多由一个键连接。不幸的是，Byteasar 的分子可能与目标分子不同。为了解决这个问题，他可以使用自己的炼金术能力。他可以随时进行两种可能的操作之一：

• Byteasar 可以选择没有键连接的两个不同原子 $a$ 和 $b$，并在它们之间形成键。由于 bytonium 的高度不稳定性，只有当前存在与 $a$ 和 $b$ 都成键的原子 $c$（不同于 $a$ 和 $b$），他才可以这样做。
• Byteasar 可以选择通过键连接的两个不同原子 $a$ 和 $b$，并移除连接它们的键。出于类似的原因，只有当前存在与 $a$ 和 $b$ 都成键的原子 $c$（不同于 $a$ 和 $b$），他才可以这样做。

Byteasar 不想在转化上花费太多时间。请编写一个程序，帮助他将自己的分子转化为目标分子，并在最多 $200\, 000$ 次操作中完成。

注意：原子两两不同，可以区分。

输入格式

第一行一个整数 $n\ (2\le n\le 30\,000)$，表示 Byteasar 拥有的分子和目标分子中原子的个数。

第二行一个整数 $m_s\ (n-1 \le m_s \le 50\, 000)$，表示 Byteasar 拥有的分子中的键数。

接下来 $m_s$ 行，每行两个整数。其中第 $i$ 行的整数 $a_i$ 和 $b_i\ (1 \le a_i , b_i \le n, a_i \neq b_i)$ 表示通过键连接的原子编号。可以保证 Byteasar 的分子是一个连贯的整体，并且每两个原子最多只通过一个键相连。

接下来一行一个整数 $m_d\ (n-1\le m_d\le 50\,000)$，表示目标分子中的键数。

接下来 $m_d$ 行包含对这些键的描述，格式与目前已拥有的分子相同。

输出格式

输出第一行包含总操作数 $r$。必须保证 $0\le r\le 200\,000$。

接下来每行包含对操作的描述。 如果你想在第 $i$ 次移动中连接原子 $x_i$ 和 $y_i$，第 $i$ 行应该以 + 号开头，在一个空格之后输出编号 $x_i$ 和 $y_i$，也用一个空格分隔。 相反，如果想删除连接 $x_i$ 和 $y_i$ 原子的键，则该行应以 - 开头，然后类似地，输出编号 $x_i$ 和 $y_i$。

输出的操作序列必须满足题目描述中给出的条件——当选择原子 $x_i$ 和 $y_i$ 时，必须有另一个原子与它们连接。执行一系列动作后，最终的分子必须与目标分子相同，即对于每对原子 $i, j\ (1 \le i < j \le n)$，如果编号为 $i$ 和 $j$ 的原子在目标分子中被一条键连接，最终状态中这对原子也应该被一条键连接。

注意，你不必最小化移动次数，你只需要最多进行 $200\,000$ 次操作即可。可以证明，总可以进行不超过 $200\,000$ 次操作来实现转化。

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

3
+ 1 3
+ 1 4
- 3 1

提示

请注意，Byteasar 无法立即连接第一个原子与第四个原子，因为当时没有原子与它们两个相连。通过在第一个和第三个原子之间建立临时键，Byteasar 就使该原子成为了第三个原子。