{"raw_statement":[{"iden":"background","content":"PA 2024 2B"},{"iden":"statement","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Alchemik Bajtazar](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/alc/)**\n\nByteasar 是一位著名的炼金术士，为了解决材料的嬗变问题，他暂时放下了制造贤者石的尝试。具体来说，Byteasar 想把一种分子转化成另一种。Byteasar 所拥有的分子由 $n$ 个 bytonium 原子组成（在 Byteotia，bytonium 是最常用的化学元素之一，主要用于生产食品和隐形眼镜），这些原子从 $1$ 到 $n$ 编号。某些原子对之间可能存在键，但每对原子之间最多只有一个键。这些分子形成了一个连贯的整体——从每个原子出发，通过一个或多个键就可以到达其他任何原子。\n\nByteasar 描述了他希望得到的 $n$ 个原子的分子中的键——对于每一对原子，他都知道是否希望它们最终由键连接。目标分子满足同样的条件——它形成一个连贯的整体，每对原子最多由一个键连接。不幸的是，Byteasar 的分子可能与目标分子不同。为了解决这个问题，他可以使用自己的炼金术能力。他可以随时进行两种可能的操作之一：\n\n- Byteasar 可以选择没有键连接的两个不同原子 $a$ 和 $b$，并在它们之间形成键。由于 bytonium 的高度不稳定性，只有当前存在与 $a$ 和 $b$ 都成键的原子 $c$（不同于 $a$ 和 $b$），他才可以这样做。\n- Byteasar 可以选择通过键连接的两个不同原子 $a$ 和 $b$，并移除连接它们的键。出于类似的原因，只有当前存在与 $a$ 和 $b$ 都成键的原子 $c$（不同于 $a$ 和 $b$），他才可以这样做。\n\nByteasar 不想在转化上花费太多时间。请编写一个程序，帮助他将自己的分子转化为目标分子，并在最多 $200\\, 000$ 次操作中完成。\n\n注意：原子两两不同，可以区分。"},{"iden":"input","content":"第一行一个整数 $n\\ (2\\le n\\le 30\\,000)$，表示 Byteasar 拥有的分子和目标分子中原子的个数。\n\n第二行一个整数 $m_s\\ (n-1 \\le m_s \\le 50\\, 000)$，表示 Byteasar 拥有的分子中的键数。\n\n接下来 $m_s$ 行，每行两个整数。其中第 $i$ 行的整数 $a_i$ 和 $b_i\\ (1 \\le a_i , b_i \\le n, a_i \\neq b_i)$ 表示通过键连接的原子编号。可以保证 Byteasar 的分子是一个连贯的整体，并且每两个原子最多只通过一个键相连。\n\n接下来一行一个整数 $m_d\\ (n-1\\le m_d\\le 50\\,000)$，表示目标分子中的键数。\n\n接下来 $m_d$ 行包含对这些键的描述，格式与目前已拥有的分子相同。"},{"iden":"output","content":"输出第一行包含总操作数 $r$。必须保证 $0\\le r\\le 200\\,000$。\n\n接下来每行包含对操作的描述。 如果你想在第 $i$ 次移动中连接原子 $x_i$ 和 $y_i$，第 $i$ 行应该以 `+` 号开头，在一个空格之后输出编号 $x_i$ 和 $y_i$，也用一个空格分隔。 相反，如果想删除连接 $x_i$ 和 $y_i$ 原子的键，则该行应以 `-` 开头，然后类似地，输出编号 $x_i$ 和 $y_i$。\n\n输出的操作序列必须满足题目描述中给出的条件——当选择原子 $x_i$ 和 $y_i$ 时，必须有另一个原子与它们连接。执行一系列动作后，最终的分子必须与目标分子相同，即对于每对原子 $i, j\\ (1 \\le i < j \\le n)$，如果编号为 $i$ 和 $j$ 的原子在目标分子中被一条键连接，最终状态中这对原子也应该被一条键连接。\n\n注意，你不必最小化移动次数，你只需要最多进行 $200\\,000$ 次操作即可。可以证明，总可以进行不超过 $200\\,000$ 次操作来实现转化。"},{"iden":"note","content":"请注意，Byteasar 无法立即连接第一个原子与第四个原子，因为当时没有原子与它们两个相连。通过在第一个和第三个原子之间建立临时键，Byteasar 就使该原子成为了第三个原子。"}],"translated_statement":null,"sample_group":[["4\n3\n1 2\n3 4\n3 2\n4\n1 4\n1 2\n2 3\n3 4\n","3\n+ 1 3\n+ 1 4\n- 3 1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}