------Read problems statements in Hindi,
Mandarin chinese
, Russian and Vietnamese as well. ------

The structure of the company ShareChat can be described by a simple graph (without multiedges and self-loops) with $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. Each vertex of this graph is part of at most one simple cycle.

For each edge, you should find the number of simple paths that contain this edge and only contain at most one edge which belongs to a cycle.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$.
$M$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $u$ and $v$, denoting the vertices connected by edge $i$.

------ Output ------
For each test case, print $M$ lines. For each $i$ ($1 ≤ i ≤ M$), the $i$-th of these lines should contain a single integer — the number of paths for edge $i$.

------ Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ u, v ≤ N$
the sum of $N+M$ for all test cases does not exceed $5 \cdot 10^{6}$

------ Subtasks ------
Subtask #1 (20 points):
the sum of answers for all edges in all test cases is smaller than $150 \cdot 10^{6}$
the sum of $N+M$ for all test cases does not exceed $5 \cdot 10^{5}$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------
2
7 7
1 2
2 3
3 4
2 5
3 5
5 6
6 7
3 3
1 2
2 3
3 1
----- Sample Output 1 ------
6
4
6
6
6
10
6
1
1
1

见题面

见题面