Divisible by 4 Spanning Tree#12898

Divisible by 4 Spanning Tree

2 seconds
256 megabytes
Hard

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

You are given a connected graph with vertices and 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.

Input

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

The first line of each test case contains two integers and (2 \le n \le 200\:000, n-1 \le m \le 200\:000)  — the numbers of nodes and edges correspondingly. The -th of the following 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 over all test cases won't exceed . The sum of over all test cases won't exceed .

Output

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

Examples

Example 1

Loading
Loading