405474: GYM101968 J Restricted Vertex Cover

You are given an undirected graph $$$G$$$ consisting of $$$n$$$ nodes and $$$m$$$ edges, each edge is either marked or unmarked.

Your job is to find out if it's possible to find any Vertex Cover of the graph, such that the marked edges can have only one of their endpoints included in the set (but not both).

A Vertex Cover is a subset of the nodes such that each edge in the graph has at least one of its endpoints in this set.

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 40$$$), the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{5}$$$) ($$$0 \leq m \leq 10^{5}$$$), the number of nodes and edges in the graph, respectively.

Each of the following $$$m$$$ lines contains three space-separated integers $$$u_{i}$$$, $$$v_{i}$$$ and $$$w_{i}$$$ ($$$1 \leq u_{i}, v_{i} \leq n$$$, $$$u_i \neq v_i$$$) ($$$0 \leq w_{i} \leq 1$$$), representing that the $$$i^{th}$$$ edge connects the nodes $$$u_{i}$$$ and $$$v_{i}$$$, and the edge is marked if $$$w_{i}$$$ is equal to $$$1$$$, otherwise it's unmarked.

For each test case, output a single line with YES if it's possible to find such a Vertex Cover, otherwise output NO.

2
5 7
1 2 1
2 3 1
3 4 0
1 3 0
2 4 1
5 3 1
5 4 1
5 6
1 2 1
1 3 1
2 4 1
4 5 1
3 5 1
2 5 0

YES
NO