ONBRIDGE - Online Bridge Searching

Given a graph of N vertices, numbered from 0 to N - 1. Initially, there is no edge in the graph. Sequentially adding M undirected edges (u, v) to the graph (0 <= u, v <= N - 1). After adding an edge, you must print out the current number of bridges in the graph. The data guarantees that there is no request to add an existed edge, or an edge from a vertex to itself.

Input

The first line contains an integer T (T <= 10) denotes the number of test cases. Each test case begins with 2 integers N (1 <= N <= 50000) and M (1 <= M <= 100000), followed by M lines, each line contains a pair of integers (u, v) represents a request to add an edge (u, v) to the graph.

Output

After each request, print out the current number of bridges in the graph on a separate line.

Example

For the input data:

1
5 10
3 0
0 2
1 0
1 3
1 4
2 4
4 0
2 1
2 3
3 4

the correct result is:

1
2
3
1
2
0
0
0
0
0


Added by:Race with time
Date:2012-03-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.