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$)，編號為 $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

請注意，Bajtazar 無法直接連接第一個原子和第四個原子，因為當時不存在同時與它們相連的原子。通過在第一個和第三個原子之間建立臨時鍵結，他使得第三個原子成為了那個中間原子。