Validate a Binary Search Tree

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

A binary tree with $n$ indexed nodes is given directly. Each node has an integer key and may have a left child and a right child.

The tree is a strict BST if, for every node with key $v$:

• every key in its entire left subtree is smaller than $v$;
• every key in its entire right subtree is greater than $v$.

The rule applies to all descendants, not only to direct children. A tree may therefore satisfy every direct parent-child comparison and still fail the BST condition because of a deeper descendant.

Determine whether the given tree is a strict BST.

Input

The first line contains $n$ and the root index $r$. If $n=0$, then $r=0$.

If $n>0$, exactly $n$ lines follow. Line $i$ describes node $i$ as key left right:

key is the key of node $i$;

left is its left-child index;

right is its right-child index.

Index $0$ means that the corresponding child is absent. Any nonzero node index is in $[1,n]$.

The input is guaranteed to describe exactly one rooted binary tree: it is connected, acyclic, and every non-root node has exactly one parent. Node keys are not guaranteed to be distinct.

Output

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

Subtasks

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

Subtask 2 (30 points): $0\le n\le 5000$.

Subtask 3 (50 points): $0\le n\le 200000$.

In all subtasks, every key is a signed 64-bit integer.

Examples

Input

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

Output

NO

Explanation

Node $1$ is the root with key $8$. Node $5$ is below node $2$, so it still belongs to the entire left subtree of the root.

However, node $5$ has key $9>8$. A key greater than $8$ appears in the root's left subtree, so the strict BST condition is violated and the output is NO.