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 maximized.
What's the maximum possible sum of $$$d(u_i, v_i)$$$ in such a partition?
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$$$ 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$$$.
For each test case, output a single integer — the largest possible sum of $$$d(u_i, v_i)$$$ in such a partition.
34 31 22 33 46 71 22 33 13 44 55 66 48 91 22 33 13 44 55 66 77 88 3
4 7 11
