← 返回题目列表

AtCoder · arc173_d

D. 支架行走

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个有向图 G 与 N 顶点和 M 边缘。顶点编号从 1 to N,每条边都标记为 ( or )。的 i第一条边从顶点定向 u_i 到顶点 v_i 带标签 c_i。该图不包含多边或自环。

在此图中,对于任意两个顶点 s 和 t,有一条路径 s to t.

判断是否存在 步行 图表上的 在图表上 G 满足以下所有条件:

  • 行走的起点和终点相同。
  • 对于 i=1,2,\dots,M, i第一条边在行走中至少使用一次。
  • 通过按照使用顺序排列行走中使用的边的标签而获得的字符串是规则的括号序列。
什么是散步? 在图表上行走 G 是一个序列 (v_1,e_1,v_2,\dots,v_{k-1},e_{k-1},v_k) of k 顶点 (k 是正整数)并且 k-1 边缘,边缘所在 e_i 从顶点定向 v_i 到顶点 v_{i+1}。顶点 v_1 和 v_k 分别称为行走的起点和终点。
什么是常规括号序列?

常规括号序列是满足以下条件之一的字符串:

  • 这是一个空字符串。
  • 连接得到的字符串 (,常规括号序列 A,和 ) 按此顺序。
  • 两个非空正则括号序列拼接而成的字符串 A 和 B 按此顺序。

约束

  • 2 \leq N \leq 4000
  • N \leq M \leq 8000
  • 1 \leq u_i,v_i \leq N
  • c_i is ( or ).
  • u_i \neq v_i
  • If i \neq j,然后 (u_i,v_i) \neq (u_j,v_j).
  • 所有输入值均为整数。
  • 在输入图中,对于任意两个顶点 s 和 t,有一条路径 s to t.

输入

输入由标准输入按以下格式给出:

N M
u_1 v_1 c_1
u_2 v_2 c_2
\vdots
u_M v_M c_M

输出

如果有满足条件的步行,则打印 Yes;否则,打印 No.


示例输入 1

5 7
1 2 (
2 3 )
3 4 (
4 1 )
2 4 )
4 5 (
5 1 )

示例输出 1

Yes

使用边缘的行走 1,2,3,4,1,5,6,7 按此顺序使用所有边至少一次,并且字符串 将边的标签按照其使用顺序排列得到的 ()()()() 是一个规则的括号序列,因此满足所有条件。

行走可能会多次使用同一条边或多次访问同一个顶点。


示例输入 2

2 2
1 2 )
2 1 )

示例输出 2

No

示例输入 3

10 20
4 5 (
5 6 (
6 7 )
2 5 )
5 8 (
6 3 )
8 5 )
1 2 (
9 10 (
4 7 (
3 4 )
8 9 (
2 1 )
1 4 )
2 3 )
3 2 (
7 8 (
7 4 )
10 9 )
9 8 )

示例输出 3

Yes