← 返回题目列表

AtCoder · awc0108_d

D. 突破安全区域

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

题目说明

一处安全区域由 N 个区组成,编号为 1 到 N。1 号区是入口,N 号区是目的地。区域内有 M 条单向通道,第 i 条通道从 U_i 通向 V_i,只有持有类型 K_i 的门禁卡才能通过。

门禁卡类型是 1 到 N 的整数。一旦取得某种卡,此后一直持有,使用时不会消耗。若 P_j=1,区 j 有一台终端,首次入侵该终端可取得类型 C_j 的卡;每台终端最多入侵一次。若 P_j=0,该区没有终端且 C_j=0。

你最初位于 1 号区且没有任何卡。在当前位置可以按任意顺序反复执行:入侵尚未使用的终端,或沿一条自己已持有所需门禁卡的出边移动。区和通道都可重复访问。请判断能否到达 N 号区。

约束

  • 2 ≤ N ≤ 100000,0 ≤ M ≤ 100000;
  • P_j 为 0 或 1;有终端时 1 ≤ C_j ≤ N,无终端时 C_j=0;
  • 1 ≤ U_i,V_i,K_i ≤ N 且 U_i ≠ V_i;
  • 输入均为整数,允许存在起点和终点相同的多条通道。

输入

N M
P_1 C_1
...
P_N C_N
U_1 V_1 K_1
...
U_M V_M K_M

输出

若能从 1 号区到达 N 号区,输出 Yes;否则输出 No。

示例

输入
4 4
1 2
1 3
0 0
0 0
1 2 2
2 4 3
1 3 1
3 4 4

输出
Yes

在入口先取得类型 2 的卡,移动到 2 号区后取得类型 3 的卡,随后即可到达 4 号区。