{"problem":{"name":"Bracket Walk","description":{"content":"You are given a directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and each edge is labeled with `(` or `)`. The $i$\\-th edge is directed from vertex $u_i$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc173_d"},"statements":[{"statement_type":"Markdown","content":"You are given a directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and each edge is labeled with `(` or `)`. The $i$\\-th edge is directed from vertex $u_i$ to vertex $v_i$ with a label $c_i$. The graph does not contain multi-edges or self-loops.\nIn this graph, for any two vertices $s$ and $t$, there is a path from $s$ to $t$.\nDetermine if there is a **walk** on the graph $G$ that satisfies all of the following conditions:\n\n*   The start and end vertices of the walk are the same.\n*   For $i=1,2,\\dots,M$, the $i$\\-th edge is used at least once in the walk.\n*   The string obtained by arranging the labels of the edges used in the walk in the order of their usage is a regular bracket sequence.\n\nWhat is a walk? A walk on a graph $G$ is a sequence $(v_1,e_1,v_2,\\dots,v_{k-1},e_{k-1},v_k)$ of $k$ vertices ($k$ is a positive integer) and $k-1$ edges, where the edge $e_i$ is directed from vertex $v_i$ to vertex $v_{i+1}$. The vertices $v_1$ and $v_k$ are called the start and end vertices of the walk, respectively. What is a regular bracket sequence?A regular bracket sequence is a string that satisfies one of the following conditions:\n\n*   It is an empty string.\n*   It is a string obtained by concatenating `(`, a regular bracket sequence $A$, and `)` in this order.\n*   It is a string obtained by concatenating two non-empty regular bracket sequences $A$ and $B$ in this order.\n\n## Constraints\n\n*   $2 \\leq N \\leq 4000$\n*   $N \\leq M \\leq 8000$\n*   $1 \\leq u_i,v_i \\leq N$\n*   $c_i$ is `(` or `)`.\n*   $u_i \\neq v_i$\n*   If $i \\neq j$, then $(u_i,v_i) \\neq (u_j,v_j)$.\n*   All input values are integers.\n*   In the input graph, for any two vertices $s$ and $t$, there is a path from $s$ to $t$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$u_1$ $v_1$ $c_1$\n$u_2$ $v_2$ $c_2$\n$\\vdots$\n$u_M$ $v_M$ $c_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc173_d","tags":[],"sample_group":[["5 7\n1 2 (\n2 3 )\n3 4 (\n4 1 )\n2 4 )\n4 5 (\n5 1 )","Yes\n\nThe walk that uses edges $1,2,3,4,1,5,6,7$ in this order uses all the edges at least once, and the string `()()()()` obtained by arranging the labels of the edges in the order of their usage is a regular bracket sequence, so all conditions are satisfied.\nThe walk may use the same edge multiple times or visit the same vertex multiple times."],["2 2\n1 2 )\n2 1 )","No"],["10 20\n4 5 (\n5 6 (\n6 7 )\n2 5 )\n5 8 (\n6 3 )\n8 5 )\n1 2 (\n9 10 (\n4 7 (\n3 4 )\n8 9 (\n2 1 )\n1 4 )\n2 3 )\n3 2 (\n7 8 (\n7 4 )\n10 9 )\n9 8 )","Yes"]],"created_at":"2026-03-03 11:01:14"}}