Kiểm tra một cây có phải BST (Validate a Binary Search Tree)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho trực tiếp một cây nhị phân có $n$ nút. Mỗi nút mang một khóa và có thể có con trái, con phải.

Cây được gọi là một BST nghiêm ngặt nếu với mọi nút có khóa $v$:

• mọi khóa trong toàn bộ cây con trái đều nhỏ hơn $v$;
• mọi khóa trong toàn bộ cây con phải đều lớn hơn $v$.

Điều kiện phải đúng với toàn bộ hậu duệ, không chỉ với hai nút con trực tiếp. Vì vậy, hai nút cha - con có thể thỏa so sánh cục bộ nhưng cây vẫn không phải BST nếu một hậu duệ nằm sai miền giá trị.

Hãy xác định cây đã cho có phải một BST nghiêm ngặt hay không.

Input

Dòng đầu chứa hai số nguyên $n$ và $r$, trong đó $r$ là chỉ số nút gốc. Nếu $n=0$ thì $r=0$.

Nếu $n>0$, tiếp theo có đúng $n$ dòng. Dòng thứ $i$ mô tả nút $i$ bằng ba giá trị key left right:

key là khóa của nút $i$;

left là chỉ số con trái của nút $i$;

right là chỉ số con phải của nút $i$.

Giá trị chỉ số bằng $0$ nghĩa là không có nút con tương ứng. Các chỉ số nút hợp lệ khác nằm trong đoạn $[1,n]$.

Dữ liệu được bảo đảm mô tả đúng một cây nhị phân có gốc $r$: không có chu trình, mọi nút đều thuộc cây và mỗi nút khác gốc có đúng một cha. Khóa của các nút không được bảo đảm phân biệt.

Output

In YES nếu cây là BST nghiêm ngặt.

Ngược lại, in NO.

Subtask

Subtask 1 (20 điểm): $0\le n\le 20$.

Subtask 2 (30 điểm): $0\le n\le 5000$.

Subtask 3 (50 điểm): $0\le n\le 200000$.

Trong tất cả các subtask, mỗi khóa là số nguyên có dấu 64-bit.

Ví dụ

Input

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

Output

NO

Giải thích

Nút $1$ là gốc và có khóa $8$. Nút $2$ nằm trong cây con trái của gốc và có khóa $3$. Nút $5$ lại nằm trong cây con của nút $2$, nên cũng thuộc toàn bộ cây con trái của khóa $8$.

Tuy nhiên nút $5$ có khóa $9>8$. Vì một khóa lớn hơn $8$ xuất hiện trong cây con trái của gốc, cây vi phạm điều kiện BST nghiêm ngặt và output là NO.