1405 - 寻找图中是否存在路径

通过次数

7

提交次数

11

Time Limit : 1 秒
Memory Limit : 128 MB

有一个具有 n 个顶点的 双向 图,其中每个顶点标记从 0n - 1(包含 0n - 1)。图中的边用一个二维整数数组 edges 表示,其中 edges[i] = [u_i, v_i] 表示顶点 u_i 和顶点 v_i 之间的双向边。 每个顶点对由 最多一条 边连接,并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始,到顶点 destination 结束的 有效路径

给你数组 edges 和整数 nsourcedestination,如果从 sourcedestination 存在 有效路径 ,则输出 true,否则输出 false

Input

第一行为一个整数n,表示edges数组的长度

以下n行,每行2个整数,分别表示每条边的顶点

第n+2行为2个整数,分别表示sourcedestination

Output

如果从 sourcedestination 存在 有效路径 ,则输出 true,否则输出 false

Examples

Input

3
0 1
1 2
2 0
0 2

Output

true

Input

5
0 1
0 2
3 5
5 4
4 3
0 5

Output

false

Hint

  • 1 <= n <= 2 * 10^5

  • 0 <= edges.length <= 2 * 10^5

  • edges[i].length == 2

  • 0 <= u_i, u_i <= n - 1

  • u_i != v_i

  • 0 <= source, destination <= n - 1

  • 不存在重复边

  • 不存在指向顶点自身的边