Lalo's Lawyer Lost

Jesus, it's always the desert.

• James McGill, Better Call Saul

While picking up Lalo's bail, Saul and Mike got lost in a desert. In a desert, they found a cactus: a connected undirected graph on $n$ nodes, such that every edge in it appears in at most one simple cycle.

It turned out that $n$ is even. For some reason, Mike and Saul want to solve the following problem:

Define $d(u, v)$ as the shortest distance between nodes $u$ and $v$ in this cactus. Partition all $n$ nodes into $\frac{n}{2}$ pairs $(u_i, v_i)$, such that every node appears in exactly one pair, and the sum of $d(u_i, v_i)$ is \textbf{maximized}.

What's the maximum possible sum of $d(u_i, v_i)$ in such a partition?

Input data

The first line contains a single integer $t$ ($1 \le t \le 10^5$) - the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n, m$ ($2 \leq n \leq 2\cdot 10^5, n-1 \leq m \leq 4\cdot 10^5$, $n$ \textbf{is even}) - the number of nodes and edges correspondingly.

The $i$-th of the next $m$ lines contains two integers $u_i, v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$) - denoting an edge between nodes $u_i$ and $v_i$. It's guaranteed that these edges form a cactus.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$, and the sum of $m$ over all test cases does not exceed $4\cdot 10^5$.

Output data

For each test case, output a single integer - the largest possible sum of $d(u_i, v_i)$ in such a partition.

Example

stdin

3
4 3
1 2
2 3
3 4
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 8
8 3

stdout

4
7
11