#1394. Chu trình Euler (TOUR)

Một ngày nọ, một họa sĩ đã vẽ một bức tranh (đồ thị), bây giờ bạn cần tìm chu trình Euler, tức là tìm một vòng trong đồ thị sao cho mỗi cạnh xuất hiện trong vòng đó đúng một lần.

Có hai bài toán con (subtasks):

1. Đồ thị là vô hướng. ( điểm)
2. Đồ thị là có hướng. ( điểm)

Dữ liệu:

• Dòng đầu tiên chứa một số nguyên , biểu thị mã bài toán con. . Nếu xử lý đồ thị vô hướng, nếu xử lý đồ thị có hướng.
• Dòng thứ hai chứa hai số nguyên , biểu thị số đỉnh và số cạnh của đồ thị.
• Tiếp theo là dòng, dòng thứ chứa hai số nguyên , biểu thị cạnh thứ (đánh số từ ). Đảm bảo .
  1. Nếu , và có một cạnh vô hướng.
  2. Nếu , có một cạnh có hướng từ đến .
• Đồ thị có thể có đa cạnh hoặc khuyên (tự vòng).

Kết quả:

• Nếu không thể vẽ được bằng một nét (không có chu trình Euler), in ra một dòng NO.
• Ngược lại, in ra một dòng YES, dòng tiếp theo in ra một phương án:
  1. Nếu , in ra số nguyên . Đặt , thì là số hiệu của cạnh thứ đi qua. Nếu dương biểu thị đi từ đến , nếu âm biểu thị đi từ đến .
  2. Nếu , in ra số nguyên . Trong đó là số hiệu của cạnh thứ đi qua.

Ví dụ:

Dữ liệu:

1
3 3
1 2
2 3
1 3

Kết quả:

YES
1 2 -3

Dữ liệu:

2
5 6
2 3
2 5
3 4
1 2
4 2
5 1

Kết quả:

YES
4 1 3 5 2 6

Giới hạn: