Problem Description

In the mathematical discipline of graph theory, a matching in a graph is a set of edges without common vertices.
You are given an undirected graph with $n$ vertices, labeled by $1,2,...,n$. Initially the graph has no edges.
There are $2$ kinds of operations :
+ u v, add an edge $(u,v)$ into the graph, multiple edges between same pair of vertices are allowed.
- u v, remove an edge $(u,v)$, it is guaranteed that there are at least one such edge in the graph.
Your task is to compute the number of matchings with exactly $k$ edges after each operation for $k=1,2,3,...,\frac{n}{2}$. Note that multiple edges between same pair of vertices are considered different.

Input

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.
In each test case, there are $2$ integers $n,m(2\leq n\leq 10,n \bmod 2=0,1\leq m\leq 30000)$, denoting the number of vertices and operations.
For the next $m$ lines, each line describes an operation, and it is guaranteed that $1\leq u<v\leq n$.

Output

For each operation, print a single line containing $\frac{n}{2}$ integers, denoting the answer for $k=1,2,3,...,\frac{n}{2}$. Since the answer may be very large, please print the answer modulo $10^9+7$.

1		
4 8	
+ 1 2
+ 3 4
+ 1 3
+ 2 4
- 1 2
- 3 4
+ 1 2
+ 3 4

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