Bajtazar là một nhà giả kim nổi tiếng, người vừa tạm gác lại những nỗ lực tạo ra hòn đá phù thủy để chuyển sang nghiên cứu sự chuyển hóa vật chất. Cụ thể, Bajtazar muốn biến đổi một phân tử này thành một phân tử khác. Phân tử mà Bajtazar đang sở hữu bao gồm $n$ nguyên tử baytonium, được đánh số từ $1$ đến $n$. Giữa một số cặp nguyên tử có thể tồn tại các liên kết, với điều kiện giữa mỗi cặp nguyên tử chỉ có tối đa một liên kết. Phân tử của Bajtazar tạo thành một khối liên kết – từ bất kỳ nguyên tử nào cũng có thể đi đến bất kỳ nguyên tử nào khác thông qua một hoặc nhiều liên kết.

Bajtazar có mô tả các liên kết cho phân tử $n$ nguyên tử mà ông muốn nhận được – đối với mỗi cặp nguyên tử, ông biết liệu mình có muốn chúng được kết nối bằng một liên kết hay không. Phân tử đích cũng thỏa mãn các điều kiện tương tự – tạo thành một khối liên kết và mỗi cặp nguyên tử được kết nối tối đa một liên kết. Thật không may, phân tử của Bajtazar có thể khác với phân tử đích. Để khắc phục điều này, ông có thể sử dụng khả năng giả kim của mình. Tại bất kỳ thời điểm nào, ông có thể thực hiện một trong hai thao tác sau:

• Bajtazar có thể chọn hai nguyên tử khác nhau $a$ và $b$ chưa được kết nối bằng liên kết và tạo một liên kết giữa chúng. Do sự mất ổn định cao của baytonium, ông chỉ có thể làm điều này nếu tồn tại một nguyên tử $c$ (khác $a$ và $b$) hiện đang được kết nối bằng các liên kết với cả $a$ và $b$.
• Bajtazar có thể chọn hai nguyên tử khác nhau $a$ và $b$ đang được kết nối bằng liên kết và xóa liên kết giữa chúng. Vì những lý do tương tự, ông chỉ có thể làm điều này nếu tồn tại một nguyên tử $c$ (khác $a$ và $b$) hiện đang được kết nối bằng các liên kết với cả $a$ và $b$.

Bajtazar không muốn dành quá nhiều thời gian cho việc chuyển hóa. Hãy viết chương trình giúp ông thực hiện việc chuyển hóa phân tử của mình thành phân tử đích trong tối đa $200\,000$ bước.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($2 \le n \le 30\,000$), biểu thị số lượng nguyên tử trong phân tử mà Bajtazar sở hữu, cũng như trong phân tử đích.

Dòng thứ hai chứa một số nguyên $m_s$ ($n-1 \le m_s \le 50\,000$), biểu thị số lượng liên kết trong phân tử mà Bajtazar sở hữu.

Trong $m_s$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), biểu thị số hiệu của các nguyên tử được kết nối bằng một liên kết. Đảm bảo rằng phân tử của Bajtazar tạo thành một khối liên kết và mỗi cặp nguyên tử được kết nối tối đa một liên kết.

Dòng tiếp theo chứa một số nguyên $m_d$ ($n-1 \le m_d \le 50\,000$), biểu thị số lượng liên kết trong phân tử đích.

Trong $m_d$ dòng tiếp theo là mô tả các liên kết đó, với định dạng tương tự như định dạng của phân tử ban đầu.

Dữ liệu ra

Dòng đầu tiên của dữ liệu ra phải chứa số lượng bước $r$ mà bạn muốn thực hiện. Phải thỏa mãn $0 \le r \le 200\,000$.

Trong mỗi $r$ dòng tiếp theo, cần có mô tả về các bước thực hiện. Nếu ở bước thứ $i$, bạn muốn kết nối hai nguyên tử $x_i$ và $y_i$ bằng một liên kết, dòng thứ $i$ phải bắt đầu bằng ký tự '+', theo sau là một khoảng trắng, rồi đến các số $x_i$ và $y_i$ cũng được ngăn cách bởi một khoảng trắng. Nếu thay vào đó bạn muốn xóa liên kết giữa hai nguyên tử $x_i$ và $y_i$, dòng đó phải bắt đầu bằng ký tự '-', theo sau là các số $x_i$ và $y_i$ tương tự.

Chuỗi các bước bạn đưa ra phải thỏa mãn các giả định đã nêu trong đề bài – tại thời điểm chọn các nguyên tử $x_i$ và $y_i$, phải tồn tại một nguyên tử khác được kết nối với cả hai nguyên tử đó. Sau khi thực hiện chuỗi các bước, phân tử cuối cùng phải giống hệt phân tử đích: đối với mỗi cặp nguyên tử $i, j$ ($1 \le i < j \le n$), các nguyên tử có số hiệu $i$ và $j$ phải được kết nối bằng một liên kết trong phân tử cuối cùng khi và chỉ khi các nguyên tử đó được kết nối bằng một liên kết trong phân tử đích.

Lưu ý rằng bạn không cần phải tối thiểu hóa số lượng bước – chỉ cần thực hiện tối đa $200\,000$ bước là đủ. Có thể chứng minh rằng việc chuyển hóa luôn có thể thực hiện được trong tối đa $200\,000$ bước.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
+ 1 3
+ 1 4
- 3 1

Ghi chú

Giải thích ví dụ: Lưu ý rằng Bajtazar không thể kết nối ngay nguyên tử thứ nhất với nguyên tử thứ tư, vì khi đó không tồn tại nguyên tử nào được kết nối với cả hai. Bằng cách tạo một liên kết tạm thời giữa nguyên tử thứ nhất và thứ ba, ông đã khiến nguyên tử thứ ba trở thành nguyên tử trung gian đó.