{"problem":{"name":"J. Restricted Vertex Cover","description":{"content":"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, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10196J"},"statements":[{"statement_type":"Markdown","content":"You are given an undirected graph $G$ consisting of $n$ nodes and $m$ edges, each edge is either marked or unmarked.\n\nYour 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).\n\nA 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.\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 40$), the number of test cases.\n\nThe first line of each test case contains two space-separated integers $n$ and $m$ ($1 <= n <= 10^5$) ($0 <= m <= 10^5$), the number of nodes and edges in the graph, respectively.\n\nEach of the following $m$ lines contains three space-separated integers $u_i$, $v_i$ and $w_i$ ($1 <= u_i, v_i <= n$, $u_i eq.not v_i$) ($0 <= w_i <= 1$), representing that the $i^(t h)$ 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.\n\nFor each test case, output a single line with *YES* if it's possible to find such a Vertex Cover, otherwise output *NO*.\n\n## Input\n\nThe first line of input contains a single integer $T$ ($1 <= T <= 40$), the number of test cases.The first line of each test case contains two space-separated integers $n$ and $m$ ($1 <= n <= 10^5$) ($0 <= m <= 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 <= u_i, v_i <= n$, $u_i eq.not v_i$) ($0 <= w_i <= 1$), representing that the $i^(t h)$ 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.\n\n## Output\n\nFor each test case, output a single line with *YES* if it's possible to find such a Vertex Cover, otherwise output *NO*.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ G = (V, E) $ be an undirected graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $, the set of nodes,  \n- $ E = E_m \\cup E_u $, the set of edges, partitioned into:  \n  - $ E_m $: marked edges ($ w_i = 1 $),  \n  - $ E_u $: unmarked edges ($ w_i = 0 $).  \n\n**Constraints**  \n1. $ 1 \\le T \\le 40 $  \n2. For each test case:  \n   - $ 1 \\le n \\le 10^5 $, $ 0 \\le m \\le 10^5 $  \n   - Each edge $ e_i = (u_i, v_i, w_i) $ satisfies $ u_i \\ne v_i $, $ w_i \\in \\{0,1\\} $  \n\n**Objective**  \nDetermine whether there exists a vertex cover $ C \\subseteq V $ such that:  \n- For every edge $ (u,v) \\in E $, $ u \\in C $ or $ v \\in C $ (standard vertex cover condition),  \n- For every marked edge $ (u,v) \\in E_m $, exactly one of $ u $ or $ v $ is in $ C $ (i.e., $ | \\{u,v\\} \\cap C | = 1 $).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10196J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}