It is the year 1692, and the people of Salem are bloodthirsty. Accusations of witchcraft are flying, and the mob is eager to see the heads of the witches on a platter. The mayor, wanting to appease the masses by minimizing the bloodbath, has decided to consult the $$$M$$$ friendships and enmities of the $$$N$$$ inhabitants: if two people are friends, then both are witches or neither is a witch, while if they are enemies, exactly one of them is a witch. Among all possible combinations of witches, the mayor will choose the one that contains the smallest number of witches. It is possible that the mayor's information is incorrect and no valid combination exists. Can you calculate how many witches will be executed?
The input consists of an integer $$$t$$$, followed by $$$t$$$ test cases. Each case starts with the integers $$$N$$$, $$$M$$$, the number of inhabitants and the number of relationships between the inhabitants. This is followed by $$$M$$$ lines, each with three integers $$$r_i$$$, $$$a_i$$$, $$$b_i$$$. If $$$r_i=1$$$, it means that inhabitants $$$a_i$$$ and $$$b_i$$$ are friends, and if $$$r_i=2$$$, then they are enemies.
One line per case with the minimum number of witches, or -1 if no valid configuration exists.
For all test cases, it holds that $$$t \leq 50$$$, $$$1 \leq N$$$, $$$0 \leq M \leq \frac{N(N - 1)}{2}$$$, $$$r_i \in \{1, 2\}$$$, $$$0 \leq a_i, b_i \lt N$$$, $$$a_i \ne b_i$$$ and for every pair of lines $$$i, j$$$, it holds that $$$a_i \ne a_j$$$ or $$$b_i \ne b_j$$$.
16 points: $$$N \leq 16$$$, $$$M \leq 30$$$
17 points: $$$N \leq 3 \cdot 10^4$$$, $$$M \leq 5 \cdot 10^4$$$, $$$r_i = 2$$$ for all i
17 points: $$$N \leq 200$$$, $$$M \leq 300$$$
50 points: $$$N \leq 3 \cdot 10^4$$$, $$$M \leq 5 \cdot 10^4$$$
3 6 5 2 0 1 2 1 2 1 1 3 2 3 4 2 4 5 5 3 1 0 1 2 2 3 2 3 4 3 3 1 0 1 1 1 2 2 0 2
3 1 -1
