405474: GYM101968 J Restricted Vertex Cover

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Restricted Vertex Covertime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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.

Output

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

ExampleInput
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
Output
YES
NO

加入题单

上一题 下一题 算法标签: