Bajtazar jest znanym alchemikiem, który chwilowo odłożył na bok próby stworzenia kamienia filozoficznego, aby zająć się transmutacją materiałów. Dokładniej, Bajtazar chciałby przeobrazić jedną cząsteczkę w drugą. Cząsteczka, którą posiada Bajtazar, składa się z $n$ atomów bajtonium, ponumerowanych od $1$ do $n$. Między niektórymi parami atomów mogą istnieć wiązania, przy czym między każdą parą atomów może istnieć co najwyżej jedno wiązanie. Cząsteczka Bajtazara tworzy spójną całość – z każdego atomu można dostać się do każdego innego, przechodząc przez jedno lub więcej wiązań.

Bajtazar posiada opis wiązań dla $n$-atomowej cząsteczki, którą chciałby otrzymać – dla każdej pary atomów wie, czy chciałby, aby były one finalnie połączone wiązaniem, czy nie. Docelowa cząsteczka spełnia te same warunki – tworzy spójną całość i każda para atomów jest połączona co najwyżej jednym wiązaniem. Niestety, cząsteczka Bajtazara może różnić się od docelowej cząsteczki. Aby temu zaradzić, może on skorzystać ze swoich alchemicznych zdolności. W każdej chwili może on wykonać jedną z dwóch możliwych operacji:

• Bajtazar może wybrać dwa różne atomy $a$ oraz $b$ niepołączone wiązaniem i stworzyć między nimi wiązanie. Ze względu na dużą niestabilność bajtonium, może to zrobić tylko wtedy, gdy istnieje atom $c$ (różny od $a$ i $b$) połączony aktualnie wiązaniami zarówno z $a$, jak i z $b$.
• Bajtazar może wybrać dwa różne atomy $a$ oraz $b$ połączone wiązaniem i usunąć wiązanie je łączące. Z podobnych względów, może to zrobić tylko wtedy, gdy istnieje atom $c$ (różny od $a$ i $b$) połączony aktualnie wiązaniami zarówno z $a$, jak i z $b$.

Bajtazar nie chce spędzić za dużo czasu nad przemianą. Napisz program, który pomoże mu dokonać przemiany jego cząsteczki w docelową i zrobi to w co najwyżej $200\,000$ ruchach.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $n$ ($2 \le n \le 30\,000$), oznaczająca liczbę atomów w cząsteczce posiadanej przez Bajtazara, jak również w tej docelowej.

W drugim wierszu wejścia znajduje się jedna liczba całkowita $m_s$ ($n-1 \le m_s \le 50\,000$), oznaczająca liczbę wiązań w cząsteczce posiadanej przez Bajtazara.

W kolejnych $m_s$ wierszach wejścia znajdują się po dwie liczby całkowite. Liczby w $i$-tym z tych wierszy, $a_i$ oraz $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), oznaczają numery atomów połączonych wiązaniem. Gwarantowanym jest, że cząsteczka Bajtazara tworzy spójną całość i każde dwa atomy mogą być połączone co najwyżej jednym wiązaniem.

W następnym wierszu wejścia znajduje się jedna liczba całkowita $m_d$ ($n-1 \le m_d \le 50\,000$), oznaczająca liczbę wiązań w docelowej cząsteczce.

W kolejnych $m_d$ wierszach znajduje się opis tychże wiązań, w formacie identycznym do formatu dla cząsteczki startowej.

Wyjście

W pierwszym wierszu wyjścia powinna znaleźć się liczba ruchów $r$, które chcesz wykonać. Musi zachodzić $0 \le r \le 200\,000$.

W każdym z kolejnych $r$ wierszy powinny znajdować się opisy kolejnych ruchów. Jeśli w $i$-tym ruchu chcesz połączyć wiązaniem atomy $x_i$ oraz $y_i$, to $i$-ty wiersz powinien zaczynać się znakiem ‘+’, a po pojedynczym odstępie powinny znaleźć się w nim liczby $x_i$ oraz $y_i$, również oddzielone pojedynczym odstępem. Jeśli zamiast tego chcesz usunąć wiązanie łączące atomy $x_i$ oraz $y_i$, to wiersz ten powinien zaczynać się znakiem ‘-’, a następnie, analogicznie, powinien on zawierać liczby $x_i$ i $y_i$.

Wypisany przez Ciebie ciąg ruchów musi spełniać założenia podane w treści – w momencie wyboru atomów $x_i$ oraz $y_i$ musi istnieć inny atom połączony z nimi oboma. Po wykonaniu ciągu ruchów, finalna cząsteczka musi być identyczna z docelową: dla każdej pary atomów $i, j$ ($1 \le i < j \le n$), atomy o numerze $i$ oraz $j$ powinny być połączone wiązaniem w finalnej cząsteczce dokładnie wtedy, gdy te atomy są połączone wiązaniem w docelowej cząsteczce.

Zwróć uwagę, że nie musisz minimalizować liczby ruchów – wystarczy, że wykonasz ich co najwyżej $200\,000$. Można udowodnić, że przemiany zawsze można dokonać, wykonując co najwyżej $200\,000$ ruchów.

Przykład

Wejście 1

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

Wyjście 1

3
+ 1 3
+ 1 4
- 3 1

Uwagi

Wyjaśnienie przykładu: Zauważ, że Bajtazar nie mógł od razu połączyć wiązaniem pierwszego atomu z czwartym, gdyż nie istniał wtedy żaden atom połączony z nimi oboma. Tworząc tymczasowe wiązanie między atomem pierwszym i trzecim, sprawił, że owym atomem stał się trzeci atom.