Is This a Binary Search Tree?

Source: HackerRank

Version: Phuoc Hung OJ Extended

Problem Statement

A binary tree is given. Every node stores an integer key.

The tree is a strict binary search tree (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 condition applies to all descendants, not only to direct children. A key several levels below a node must still satisfy all bounds imposed by its ancestors.

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. Child index $0$ means that the child is absent; every nonzero child index lies in $[1,n]$.

The input is guaranteed to describe a valid rooted binary tree: it is connected, acyclic, and every non-root node has exactly one parent. Its key arrangement may violate the BST condition.

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 node 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

The node with key $9$ belongs to the left subtree of the root with key $8$. Every key in that subtree must be smaller than $8$, but $9>8$.

Therefore the tree is not a strict BST and the program prints NO.