Validate Binary Search Tree

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

A binary tree with $n$ nodes is given. It is a valid BST if all of the following conditions hold at every node with key $v$:

• every key in the left subtree is strictly smaller than $v$;
• every key in the right subtree is strictly greater than $v$;
• both subtrees satisfy the same definition.

The inequalities are strict, so two equal keys cannot both appear in a valid BST.

Determine whether the given tree is a valid BST.

Input

The first line contains $n$ and the root index $r$.

Exactly $n$ lines follow. Line $i$ describes node $i$ as key left right. A child index of $0$ means that the child is absent; any nonzero child index is in $[1,n]$.

The input is guaranteed to describe exactly one connected, acyclic binary tree rooted at $r$.

Output

Print YES if the tree is a valid BST; otherwise print NO.

Subtasks

Subtask 1 (20 points): $1\le n\le 20$.

Subtask 2 (30 points): $1\le n\le 500$.

Subtask 3 (50 points): $1\le n\le 10^4$.

In all subtasks, $-2^{31}\le \text{key}\le 2^{31}-1$.

Examples

Input

5 1
8 2 3
3 4 5
10 0 0
1 0 0
9 0 0

Output

NO

Explanation

The node with key $9$ is in the left subtree of the root with key $8$. A valid BST requires every key in that entire subtree to be smaller than $8$, but $9>8$.

Therefore the tree is invalid and the output is NO.