#882 double eulerian circuit

Statement

Statement language

You are given a connected simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$ .

Find a closed walk that traverses every edge exactly twice. Two consecutive traversals must not use the same edge. The last and first traversals must also use different edges.

Definition of a Walk

A walk in a graph is a sequence of vertices $w_0,w_1,\cdots,w_k$ such that an edge exists between and for every (). A walk may visit the same vertex or traverse the same edge multiple times.

There is no restriction on the direction in which an edge is traversed. If no such closed walk exists, report that it is impossible.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, if no valid closed walk exists, print NO on one line.

Otherwise, print YES on the first line. On the second line, print the visited vertices $w_0,w_1,\cdots,w_{2M}$ , separated by spaces.

Constraints

$1 \leq T \leq 2\,000$ .
$2 \leq N \leq 2\,000$ .
$N - 1 \leq$ .

Subtasks

#	Score	Constraints
1	18	$M\leq6$ , $\sum M\leq200$ .
2	17	Every vertex has degree at most $2$ .
3	65

Samples

Input

Output

YES
1 3 2 1 3 2 1
NO
YES
1 3 4 6 5 4 6 5 4 3 2 1 3 2 1

One answer for the first test case is $1,2,3,1,2,3,1$ . The second test case has no valid closed walk.