Bajtazar is a well-known alchemist who has temporarily set aside his attempts to create the philosopher's stone to focus on the transmutation of materials. More precisely, Bajtazar would like to transform one molecule into another. The molecule Bajtazar possesses consists of $n$ atoms of "baytonium", numbered from $1$ to $n$. Bonds may exist between some pairs of atoms, with at most one bond between any pair of atoms. Bajtazar's molecule forms a connected whole – it is possible to get from any atom to any other by passing through one or more bonds.

Bajtazar has a description of the bonds for the $n$-atom molecule he would like to obtain – for every pair of atoms, he knows whether he wants them to be connected by a bond or not. The target molecule satisfies the same conditions – it forms a connected whole and every pair of atoms is connected by at most one bond. Unfortunately, Bajtazar's molecule may differ from the target molecule. To fix this, he can use his alchemical abilities. At any moment, he can perform one of two possible operations:

• Bajtazar can choose two different atoms $a$ and $b$ that are not connected by a bond and create a bond between them. Due to the high instability of baytonium, he can only do this if there exists an atom $c$ (different from $a$ and $b$) currently connected by bonds to both $a$ and $b$.
• Bajtazar can choose two different atoms $a$ and $b$ connected by a bond and remove the bond connecting them. For similar reasons, he can only do this if there exists an atom $c$ (different from $a$ and $b$) currently connected by bonds to both $a$ and $b$.

Bajtazar does not want to spend too much time on the transformation. Write a program that will help him transform his molecule into the target one in at most $200\,000$ moves.

Input

The first line of input contains a single integer $n$ ($2 \le n \le 30\,000$), representing the number of atoms in the molecule possessed by Bajtazar, as well as in the target one.

The second line of input contains a single integer $m_s$ ($n-1 \le m_s \le 50\,000$), representing the number of bonds in the molecule possessed by Bajtazar.

The next $m_s$ lines of input each contain two integers. The numbers in the $i$-th of these lines, $a_i$ and $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), represent the numbers of the atoms connected by a bond. It is guaranteed that Bajtazar's molecule forms a connected whole and that any two atoms can be connected by at most one bond.

The next line of input contains a single integer $m_d$ ($n-1 \le m_d \le 50\,000$), representing the number of bonds in the target molecule.

The next $m_d$ lines contain the description of these bonds, in a format identical to the format for the starting molecule.

Output

The first line of the output should contain the number of moves $r$ you wish to perform. It must hold that $0 \le r \le 200\,000$.

Each of the next $r$ lines should contain the descriptions of the subsequent moves. If in the $i$-th move you want to connect atoms $x_i$ and $y_i$ with a bond, the $i$-th line should start with the character '+', followed by a single space, and then the numbers $x_i$ and $y_i$, also separated by a single space. If instead you want to remove the bond connecting atoms $x_i$ and $y_i$, the line should start with the character '-', followed by the numbers $x_i$ and $y_i$ in the same manner.

The sequence of moves you output must satisfy the assumptions given in the problem statement – at the moment of choosing atoms $x_i$ and $y_i$, there must exist another atom connected to both of them. After performing the sequence of moves, the final molecule must be identical to the target one: for every pair of atoms $i, j$ ($1 \le i < j \le n$), the atoms numbered $i$ and $j$ should be connected by a bond in the final molecule if and only if these atoms are connected by a bond in the target molecule.

Note that you do not have to minimize the number of moves – it is sufficient to perform at most $200\,000$ of them. It can be proven that the transformation can always be performed in at most $200\,000$ moves.

Examples

Input 1

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

Output 1

3
+ 1 3
+ 1 4
- 3 1

Note 1

Explanation of the example: Note that Bajtazar could not immediately connect the first atom with the fourth, because there was no atom connected to both of them at that time. By creating a temporary bond between the first and third atom, he made the third atom that common atom.