410788: GYM104114 D Divisible by 4 Spanning Tree
Description
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.
InputThe 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$$$.
OutputFor each test case, output if YES, if such spanning tree exists, and NO otherwise.
ExampleInput4 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 8Output
NO YES YES NO