#GT012. 寻找图中是否存在路径

寻找图中是否存在路径

说明

有一个具有 nn 个顶点的 双向 图,其中每个顶点标记从 00n1n - 1(包含 00n1n - 1)。图中的边用一个长度为 mm 的二维整数数组 edgesedges 表示,其中 edgesi=(ui,vi)edges_i = (u_i, v_i) 表示顶点 uiu_i 和顶点 viv_i 之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 ss 开始,到顶点 ee 结束的 有效路径,存在输出 yes,否则输出 no

输入

第一行两个整数 nnmm; 接下来 mm 行,每行两个整数 u,vu, v,分别表示有连接的两个顶点; 最后一行两个整数 s,es, e

输出

yes 或者 no,即 ssee 之间是否有路径。

样例

3 3
0 1
1 2
2 0
0 2
yes
6 5
0 1
3 5
2 0
4 5
4 3
0 5
no

提示

样例说明

样例一

image

解释:存在由顶点 00 到顶点 22 的路径。

  • 0120 → 1 → 2
  • 020 → 2

样例二

image

解释:不存在由顶点 0 到顶点 5 的路径。

数据范围

  • 1n2×1051\leq n\leq 2 \times 10^5
  • 0m2×1050\leq m\leq 2 \times 10^5
  • 0u,vn10\leq u,v \leq n-1
  • uvu \neq v
  • 0s,en10\leq s,e \leq n-1
  • 不存在重复边
  • 不存在指向顶点自身的边