Bajtazar est un alchimiste renommé qui a temporairement mis de côté ses tentatives de création de la pierre philosophale pour se consacrer à la transmutation des matériaux. Plus précisément, Bajtazar souhaite transformer une molécule en une autre. La molécule qu'il possède se compose de $n$ atomes de bajtonium*, numérotés de 1 à $n$. Entre certaines paires d'atomes, il peut exister des liaisons, sachant qu'il ne peut y avoir au plus qu'une seule liaison entre chaque paire d'atomes. La molécule de Bajtazar forme un tout cohérent : à partir de n'importe quel atome, il est possible d'atteindre n'importe quel autre atome en passant par une ou plusieurs liaisons.

Bajtazar possède la description des liaisons pour la molécule à $n$ atomes qu'il souhaite obtenir ; pour chaque paire d'atomes, il sait s'il souhaite qu'ils soient finalement reliés par une liaison ou non. La molécule cible remplit les mêmes conditions : elle forme un tout cohérent et chaque paire d'atomes est reliée par au plus une liaison. Malheureusement, la molécule de Bajtazar peut différer de la molécule cible. Pour y remédier, il peut utiliser ses capacités alchimiques. À tout moment, il peut effectuer l'une des deux opérations suivantes :

• Bajtazar peut choisir deux atomes distincts $a$ et $b$ non reliés par une liaison et créer une liaison entre eux. En raison de la grande instabilité du bajtonium, il ne peut le faire que s'il existe un atome $c$ (distinct de $a$ et $b$) actuellement relié par des liaisons à la fois à $a$ et à $b$.
• Bajtazar peut choisir deux atomes distincts $a$ et $b$ reliés par une liaison et supprimer la liaison qui les unit. Pour des raisons similaires, il ne peut le faire que s'il existe un atome $c$ (distinct de $a$ et $b$) actuellement relié par des liaisons à la fois à $a$ et à $b$.

Bajtazar ne veut pas passer trop de temps sur la transformation. Écrivez un programme qui l'aidera à transformer sa molécule en la molécule cible en effectuant au plus 200 000 mouvements.

Entrée

La première ligne de l'entrée contient un entier $n$ ($2 \le n \le 30\,000$), représentant le nombre d'atomes dans la molécule possédée par Bajtazar, ainsi que dans la molécule cible.

La deuxième ligne de l'entrée contient un entier $m_s$ ($n-1 \le m_s \le 50\,000$), représentant le nombre de liaisons dans la molécule initiale de Bajtazar.

Les $m_s$ lignes suivantes de l'entrée contiennent chacune deux entiers. Les nombres dans la $i$-ième de ces lignes, $a_i$ et $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), indiquent les numéros des atomes reliés par une liaison. Il est garanti que la molécule de Bajtazar forme un tout cohérent et que deux atomes quelconques peuvent être reliés par au plus une liaison.

La ligne suivante de l'entrée contient un entier $m_d$ ($n-1 \le m_d \le 50\,000$), représentant le nombre de liaisons dans la molécule cible.

Les $m_d$ lignes suivantes contiennent la description de ces liaisons, dans un format identique à celui de la molécule initiale.

Sortie

La première ligne de la sortie doit contenir le nombre de mouvements $r$ que vous souhaitez effectuer. Il doit satisfaire $0 \le r \le 200\,000$.

Chacune des $r$ lignes suivantes doit contenir la description des mouvements successifs. Si, lors du $i$-ième mouvement, vous souhaitez créer une liaison entre les atomes $x_i$ et $y_i$, la $i$-ième ligne doit commencer par le signe '+', suivi d'un espace, puis des nombres $x_i$ et $y_i$ séparés par un espace. Si, au contraire, vous souhaitez supprimer la liaison reliant les atomes $x_i$ et $y_i$, la ligne doit commencer par le signe '-', suivi, de la même manière, des nombres $x_i$ et $y_i$.

La séquence de mouvements que vous affichez doit respecter les conditions énoncées dans l'énoncé : au moment du choix des atomes $x_i$ et $y_i$, il doit exister un autre atome relié aux deux. Après avoir effectué la séquence de mouvements, la molécule finale doit être identique à la cible : pour chaque paire d'atomes $i, j$ ($1 \le i < j \le n$), les atomes numérotés $i$ et $j$ doivent être reliés par une liaison dans la molécule finale si et seulement s'ils sont reliés par une liaison dans la molécule cible.

Notez que vous n'avez pas besoin de minimiser le nombre de mouvements ; il suffit d'en effectuer au plus 200 000. Il est possible de prouver que la transformation peut toujours être effectuée en un maximum de 200 000 mouvements.

Exemples

Entrée 1

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

Sortie 1

3
+ 1 3
+ 1 4
- 3 1

Remarque 1

Notez que Bajtazar ne pouvait pas relier directement le premier atome au quatrième, car il n'existait alors aucun atome relié aux deux. En créant une liaison temporaire entre le premier et le troisième atome, il a fait en sorte que le troisième atome devienne cet intermédiaire.

\ En Bajtonie, le bajtonium est l'un des éléments chimiques les plus populaires, utilisé entre autres pour la production de nourriture et de lentilles de contact.*