You are given a graph $G$ consisting of $N$ vertices numbered $1, 2, \ldots, N$. Initially, $G$ has no edges.
You will add $M$ undirected edges to $G$. The final shape of the graph is predetermined, and the $i$\-th edge to be added $(1 ≤ i ≤ M)$ connects vertices $u_i$ and $v_i$. We will refer to this as edge $i$.
It is guaranteed that the resulting graph will be simple.
Determine if there exists a permutation $(P_1, P_2, \ldots, P_M)$ of $(1, 2, \ldots, M)$ that satisfies the following conditions, and if such a permutation exists, show an example.
> **Conditions**
> You must be able to add all $M$ edges to $G$ by following this procedure:
>
> * For $i = 1, 2, \dots, M$, repeat the following:
> 1. If there is already a cycle in $G$ containing either vertex $u_{P_i}$ or vertex $v_{P_i}$, the condition is not satisfied, and the procedure ends.
> 2. Add edge $P_i$ (the undirected edge connecting $u_{P_i}$ and $v_{P_i}$) to $G$.
You are given $T$ test cases; solve each of them.
What is a cycle? A cycle in $G$ is defined as a sequence of vertices $(v_0, \dots, v_{L - 1})$ and a sequence of edges $(e_0, \dots, e_{L - 1})$ that satisfy the following conditions:
* $L \ge 1$
* $i \neq j \implies v_i \neq v_j, e_i \neq e_j$
* For $0 \le i \le L - 2$, edge $e_i$ connects vertices $v_i$ and $v_{i+1}$
* Edge $e_{L-1}$ connects vertices $v_{L-1}$ and $v_0$
What does it mean for a graph to be simple? A graph $G$ is simple if it contains no self-loops or multiple edges.
## Constraints
* All input values are integers.
* $1 \le T \le 2000$
* For each test case:
* $2 \le N \le 4000$
* $1 \le M \le 4000$
* $1 \le u_i, v_i \le N\ (1 ≤ i ≤ M)$
* The graph formed by adding all given edges is simple.
* The sum of $N$ over all test cases is at most $4000$.
* The sum of $M$ over all test cases is at most $4000$.
## Input
The input is given from Standard Input in the following format:
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Here, $\text{case}_i\ (1 ≤ i ≤ T)$ represents the $i$\-th test case. Each test case is given in the following format:
$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
## Subtasks
$30$ points will be awarded for passing the test set satisfying:
* $T \le 50$
* For each test case:
* $N \le 100$
* $M \le 100$
* The sum of $N$ over all test cases is at most $100$.
* The sum of $M$ over all test cases is at most $100$.
[samples]