Description

Original source: UOJ #117

One day, a soulful artist drew a graph. Now, you are asked to find an Eulerian circuit, i.e., a cycle in the graph where each edge appears exactly once.

There are two subtasks:

1. The graph is undirected. (50 points)

2. The graph is directed. (50 points)

Input Format

The first line contains an integer $t$, representing the subtask number. $t \in \{1, 2\}$, where $t = 1$ indicates the undirected graph case, and $t = 2$ indicates the directed graph case.

The second line contains two integers $n, m$, representing the number of nodes and edges in the graph.

In the next $m$ lines, the $i$-th line contains two integers $v_i, u_i$, representing the $i$-th edge (numbered starting from 1). It is guaranteed that $1 \leq v_i, u_i \leq n$.

1. If $t = 1$, it means there is an undirected edge between $v_i$ and $u_i$.

2. If $t = 2$, it means there is a directed edge from $v_i$ to $u_i$.

The graph may contain multiple edges and self-loops.

Output Format

If it is impossible to draw the graph in one stroke, output a single line NO.

Otherwise, output a line YES, followed by a line describing the solution.

1. If $t = 1$, output $m$ integers $p_1, p_2, \dots, p_m$. Let $e = \lvert p_i \rvert$, then $e$ represents the index of the $i$-th edge traversed. If $p_i$ is positive, it means moving from $v_e$ to $u_e$; otherwise, it means moving from $u_e$ to $v_e$.

2. If $t = 2$, output $m$ integers $p_1, p_2, \dots, p_m$, where $p_i$ represents the index of the $i$-th edge traversed.

Sample 1

1
3 3
1 2
2 3
1 3

YES
1 2 -3

Sample 2

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

YES
4 1 3 5 2 6

Data Range and Hints

$1 \leq n \leq 10^5, 0 \leq m \leq 2 \times 10^5$