← 返回 google 的题目列表Intersection of Two Family Chains (find common ancestor/member)
类型：online_judge
Problem: Do Two Family Chains Intersect?
You are given two “family chains” chainA and chainB. Each chain is a singly linked path obtained by repeatedly following a parent pointer from a starting person up to ancestors.
Each node has:
id (unique)
parent pointer (or null)
Determine whether the two chains intersect, i.e., whether there exists a node x that appears in both ancestor paths.
Input (stdin)
Line 1: integer n (number of nodes)
Line 2: integer p (number of parent relations)
Next p lines: child parent (parent = -1 means null)
Last two lines: startA, startB
Output (stdout)
Print one line:
YES if they intersect
NO otherwise
Constraints
1 <= n <= 2e5
Each node has at most one parent
Example
Input:
6
5
1 3
2 3
3 5
4 5
5 -1
1
4
Output:
YES
Example
Input
6
5
1 3
2 3
3 5
4 5
5 -1
1
4
Output
YES