Bajtazar 是一位著名的炼金术士，他暂时搁置了制造贤者之石的尝试，转而研究物质的嬗变。更确切地说，Bajtazar 希望将一个分子转化为另一个分子。

Bajtazar 拥有的分子由 $n$ 个拜顿原子（bajtonium）组成，编号从 $1$ 到 $n$。某些原子对之间可能存在化学键，每对原子之间最多只能存在一个化学键。Bajtazar 的分子是一个连通整体——从任何一个原子出发，通过一个或多个化学键，都可以到达其他任何原子。

Bajtazar 拥有他想要得到的 $n$ 原子分子的化学键描述——对于每一对原子，他都知道它们最终是否应该通过化学键连接。目标分子满足相同的条件——它是一个连通整体，且每对原子之间最多通过一个化学键连接。遗憾的是，Bajtazar 当前的分子可能与目标分子不同。为了解决这个问题，他可以利用自己的炼金术能力。在任何时候，他都可以执行以下两种操作之一：

• Bajtazar 可以选择两个尚未通过化学键连接的不同原子 $a$ 和 $b$，并在它们之间建立一个化学键。由于拜顿原子的极度不稳定，只有当存在一个同时与 $a$ 和 $b$ 均有化学键连接的原子 $c$（$c \neq a, b$）时，他才能执行此操作。
• Bajtazar 可以选择两个通过化学键连接的不同原子 $a$ 和 $b$，并移除它们之间的化学键。出于同样的原因，只有当存在一个同时与 $a$ 和 $b$ 均有化学键连接的原子 $c$（$c \neq a, b$）时，他才能执行此操作。

Bajtazar 不想在转化上花费太多时间。请编写一个程序，帮助他将当前分子转化为目标分子，且操作次数不超过 $200\,000$ 次。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 30\,000$)，表示 Bajtazar 当前分子以及目标分子中的原子数量。

第二行包含一个整数 $m_s$ ($n-1 \le m_s \le 50\,000$)，表示 Bajtazar 当前分子中的化学键数量。

接下来的 $m_s$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$)，表示通过化学键连接的原子编号。保证 Bajtazar 的分子是一个连通整体，且每对原子之间最多通过一个化学键连接。

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

接下来的 $m_d$ 行，格式与初始分子相同，描述了目标分子中的化学键。

输出格式

第一行应输出你想要执行的操作次数 $r$。必须满足 $0 \le r \le 200\,000$。

在接下来的 $r$ 行中，每行应包含一个操作的描述。如果你想在第 $i$ 次操作中连接原子 $x_i$ 和 $y_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$)，当且仅当它们在目标分子中通过化学键连接时，它们在最终分子中才应通过化学键连接。

请注意，你不需要最小化操作次数——只需确保操作次数不超过 $200\,000$ 即可。可以证明，通过不超过 $200\,000$ 次操作，总是可以完成转化。

样例

输入 1

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

输出 1

3
+ 1 3
+ 1 4
- 3 1

说明 1

注意，Bajtazar 不能直接连接第一个原子和第四个原子，因为当时不存在同时与它们连接的原子。通过在第一个原子和第三个原子之间建立临时化学键，他使得第三个原子成为了那个中间原子。