There are $$$n$$$ red pandas sitting around a table, numbered from $$$1$$$ to $$$n$$$ in a clockwise order. There are $$$k$$$ initial partnerships, each of which connects two red pandas. Partnerships can be represented in a straight line between two red pandas.
In the end, the red pandas want a total of $$$\frac{n}{2}$$$ partnerships such that each red panda is in exactly $$$1$$$ partnership, such that no two lines representing partnerships intersect (otherwise, they would have to talk over each other)!
Of course, with their initial partnerships, it may not always be possible to form a valid final configuration of partnerships. Please find the minimum initial partnerships that the red pandas have to break in order to reach their goal.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$n$$$ even, $$$2 \leq n \leq 10^5$$$, $$$0 \leq 2k \leq n$$$).
The next $$$k$$$ lines of every test case includes two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$), indicating an initial partnership. It is guaranteed that no red panda will be included in more than one initial partnership, and no two initial partnerships intersect.
It is guaranteed that the sum of all $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one number: the minimum initial partnerships that must be broken.
34 11 320 06 31 23 45 6
1 0 0
In the first test case, we must remove the existing partnership, otherwise the other two red pandas cannot have partners.
In the second test case, there are no initial partnerships to remove, so our answer is $$$0$$$.
In the third test case, our existing partnerships already give every red panda a valid partner, so our answer is also $$$0$$$.
