바이자르는 연금술사로, 잠시 현자의 돌을 만드는 연구를 미뤄두고 물질 변환에 집중하기로 했습니다. 더 구체적으로 말하자면, 바이자르는 한 분자를 다른 분자로 변환하고자 합니다. 바이자르가 가진 분자는 $1$부터 $n$까지 번호가 매겨진 $n$개의 바이트늄(bajtonium)* 원자로 구성되어 있습니다. 원자 쌍 사이에는 결합이 존재할 수 있으며, 각 원자 쌍 사이에는 최대 하나의 결합만 존재할 수 있습니다. 바이자르의 분자는 연결된 전체 구조를 이루고 있어, 어떤 원자에서든 하나 이상의 결합을 거쳐 다른 모든 원자로 이동할 수 있습니다.

바이자르는 자신이 얻고자 하는 $n$개 원자로 구성된 분자의 결합 정보를 알고 있습니다. 즉, 모든 원자 쌍에 대해 최종적으로 결합이 있기를 원하는지 여부를 알고 있습니다. 목표 분자 역시 동일한 조건, 즉 연결된 전체 구조를 이루며 각 원자 쌍 사이에는 최대 하나의 결합만 존재한다는 조건을 만족합니다. 안타깝게도 바이자르의 현재 분자는 목표 분자와 다를 수 있습니다. 이를 해결하기 위해 그는 자신의 연금술 능력을 사용할 수 있습니다. 그는 언제든지 다음 두 가지 작업 중 하나를 수행할 수 있습니다.

• 바이자르는 결합으로 연결되지 않은 서로 다른 두 원자 $a$와 $b$를 선택하여 그 사이에 결합을 생성할 수 있습니다. 바이트늄의 높은 불안정성 때문에, 이 작업은 현재 $a$와 $b$ 모두와 결합되어 있는 원자 $c$($a$ 및 $b$와는 다른 원자)가 존재할 때만 가능합니다.
• 바이자르는 결합으로 연결된 서로 다른 두 원자 $a$와 $b$를 선택하여 그 사이의 결합을 제거할 수 있습니다. 비슷한 이유로, 이 작업은 현재 $a$와 $b$ 모두와 결합되어 있는 원자 $c$($a$ 및 $b$와는 다른 원자)가 존재할 때만 가능합니다.

바이자르는 변환에 너무 많은 시간을 쓰고 싶어 하지 않습니다. 그의 분자를 목표 분자로 변환하되, 최대 $200\,000$번의 이동 이내에 완료하는 프로그램을 작성하세요.

입력

첫 번째 줄에는 바이자르가 가진 분자와 목표 분자의 원자 수를 나타내는 정수 $n$ ($2 \le n \le 30\,000$)이 주어집니다.

두 번째 줄에는 바이자르가 가진 분자의 결합 수를 나타내는 정수 $m_s$ ($n-1 \le m_s \le 50\,000$)가 주어집니다.

이어지는 $m_s$개의 줄에는 각각 두 개의 정수 $a_i$와 $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$)가 주어지며, 이는 결합으로 연결된 원자 번호를 나타냅니다. 바이자르의 분자는 연결된 전체 구조를 이루며, 임의의 두 원자 사이에는 최대 하나의 결합만 존재함이 보장됩니다.

다음 줄에는 목표 분자의 결합 수를 나타내는 정수 $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

참고

예제 설명: 바이자르는 첫 번째 원자와 네 번째 원자를 즉시 결합할 수 없었습니다. 당시 두 원자 모두와 결합된 원자가 존재하지 않았기 때문입니다. 첫 번째 원자와 세 번째 원자 사이에 임시 결합을 생성함으로써, 세 번째 원자가 그 역할을 수행하게 되었습니다.

*바이트니아에서 바이트늄은 식품 및 콘택트렌즈 생산 등에 사용되는 가장 대중적인 화학 원소 중 하나입니다.