錬金術師バイタザールは、賢者の石を作る試みを一時中断し、物質の変換に取り組むことにしました。具体的には、バイタザールはある分子を別の分子に変換したいと考えています。バイタザールが所有する分子は $n$ 個のバイトニウム原子からなり、それぞれ $1$ から $n$ まで番号が振られています。原子のペアの間には結合が存在することがあり、どのペアの間にも最大で 1 つの結合しか存在しません。バイタザールの分子は連結しており、どの原子からどの原子へも、1 つ以上の結合をたどることで到達可能です。
バイタザールは、変換後の $n$ 原子分子の結合状態についても記述を持っています。つまり、どの原子ペアが最終的に結合しているべきかを知っています。目標の分子も同様に連結しており、どの原子ペアの間にも最大で 1 つの結合しか存在しません。残念ながら、バイタザールの現在の分子は目標の分子と異なる場合があります。これを解決するために、彼は錬金術の能力を使うことができます。彼はいつでも以下の 2 つの操作のうちいずれか 1 つを実行できます。
- 結合していない 2 つの異なる原子 $a$ と $b$ を選び、それらの間に結合を作成する。バイトニウムの不安定さのため、これは $a$ と $b$ の両方と現在結合している原子 $c$ ($a, b$ とは異なる) が存在する場合にのみ可能です。
- 結合している 2 つの異なる原子 $a$ と $b$ を選び、それらの間の結合を削除する。同様の理由で、これは $a$ と $b$ の両方と現在結合している原子 $c$ ($a, b$ とは異なる) が存在する場合にのみ可能です。
バイタザールは変換にあまり時間をかけたくありません。彼の分子を目標の分子に変換し、その操作回数が最大 200,000 回以内となるようなプログラムを作成してください。
入力
入力の最初の行には、バイタザールが所有する分子および目標の分子に含まれる原子の数 $n$ ($2 \le n \le 30,000$) が与えられます。
2 行目には、バイタザールが所有する分子の結合数 $m_s$ ($n-1 \le m_s \le 50,000$) が与えられます。
続く $m_s$ 行には、それぞれ 2 つの整数が与えられます。$i$ 番目の行の $a_i$ と $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$) は、結合されている原子の番号を表します。バイタザールの分子は連結しており、どの 2 つの原子間にも最大で 1 つの結合しか存在しないことが保証されています。
次の行には、目標の分子の結合数 $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$) について、最終的な分子において原子 $i$ と $j$ が結合しているのは、目標の分子においてそれらが結合している場合かつその場合に限られます。
操作回数を最小化する必要はないことに注意してください。最大 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 原子と第 4 原子を直接結合することはできませんでした。なぜなら、その時点では両方と結合している原子が存在しなかったからです。第 1 原子と第 3 原子の間に一時的な結合を作成することで、第 3 原子がその役割を果たすようになります。