410788: GYM104114 D Divisible by 4 Spanning Tree

A tree $$$T$$$ is special if the number of vertices with an odd degree (with respect to $$$T$$$) is a multiple of $$$4$$$.

You are given a connected graph with $$$n$$$ vertices and $$$m$$$ edges. Determine if there is a special spanning tree in this graph.

As a reminder, a spanning tree of a graph is a subset of the edges of the graph that forms a tree.

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10\:000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(2 \le n \le 200\:000$$$, $$$n-1 \le m \le 200\:000)$$$  — the numbers of nodes and edges correspondingly. The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$u_i, v_i$$$ $$$(1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i)$$$, indicating that there is an edge between nodes $$$u_i$$$ and $$$v_i$$$.

No edge will appear multiple times inside a test case. The sum of $$$n$$$ over all test cases won't exceed $$$200\:000$$$. The sum of $$$m$$$ over all test cases won't exceed $$$400\:000$$$.

For each test case, output if YES, if such spanning tree exists, and NO otherwise.

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

NO
YES
YES
NO