Бальтазар — известный алхимик, который на время отложил попытки создания философского камня, чтобы заняться трансмутацией материалов. Точнее, Бальтазар хотел бы превратить одну молекулу в другую. Молекула, которой владеет Бальтазар, состоит из $n$ атомов байтония*, пронумерованных от $1$ до $n$. Между некоторыми парами атомов могут существовать связи, при этом между любой парой атомов может быть не более одной связи. Молекула Бальтазара представляет собой связное целое — из каждого атома можно добраться до любого другого, пройдя по одной или нескольким связям.

Бальтазар имеет описание связей для $n$-атомной молекулы, которую он хотел бы получить — для каждой пары атомов он знает, должны ли они быть в итоге соединены связью или нет. Целевая молекула удовлетворяет тем же условиям — она представляет собой связное целое, и каждая пара атомов соединена не более чем одной связью. К сожалению, молекула Бальтазара может отличаться от целевой. Чтобы это исправить, он может воспользоваться своими алхимическими способностями. В любой момент он может выполнить одну из двух возможных операций:

• Бальтазар может выбрать два различных атома $a$ и $b$, не соединенных связью, и создать между ними связь. Из-за высокой нестабильности байтония он может сделать это только в том случае, если существует атом $c$ (отличный от $a$ и $b$), который в данный момент соединен связями как с $a$, так и с $b$.
• Бальтазар может выбрать два различных атома $a$ и $b$, соединенных связью, и удалить эту связь. По тем же причинам он может сделать это только в том случае, если существует атом $c$ (отличный от $a$ и $b$), который в данный момент соединен связями как с $a$, так и с $b$.

Бальтазар не хочет тратить слишком много времени на превращение. Напишите программу, которая поможет ему превратить его молекулу в целевую, сделав это не более чем за $200\,000$ ходов.

Входные данные

В первой строке входных данных находится одно целое число $n$ ($2 \le n \le 30\,000$), обозначающее количество атомов в молекуле, которой владеет Бальтазар, а также в целевой молекуле.

Во второй строке входных данных находится одно целое число $m_s$ ($n-1 \le m_s \le 50\,000$), обозначающее количество связей в молекуле, которой владеет Бальтазар.

В следующих $m_s$ строках входных данных содержатся по два целых числа. Числа в $i$-й из этих строк, $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$, то $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

3
+ 1 3
+ 1 4
- 3 1

Примечание

Пояснение к примеру: Заметьте, что Бальтазар не мог сразу соединить связью первый атом с четвертым, так как в тот момент не существовало ни одного атома, соединенного с ними обоими. Создав временную связь между первым и третьим атомами, он сделал третьим атомом тот самый атом, который был нужен.

* В Байтоции байтоний является одним из самых популярных химических элементов, используемым, среди прочего, для производства продуктов питания и контактных линз.