题目说明
一处安全区域由 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 号区。