Cây này có phải BST? (Is This a Binary Search Tree?)

Nguồn: HackerRank

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

Đề bài

Cho một cây nhị phân. Mỗi nút mang một khóa số nguyên.

Cây là một cây tìm kiếm nhị phân (BST) nghiêm ngặt khi, 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 được xét trên toàn bộ cây con, không chỉ trên hai cạnh nối trực tiếp từ một nút tới các con của nó. Do đó một khóa nằm sâu hơn nhiều mức vẫn phải thỏa mọi giới hạn do các tổ tiên của nó tạo ra.

Hãy xác định cây đã cho có thỏa định nghĩa BST nghiêm ngặt hay không.

Input

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

Nếu $n>0$, tiếp theo có $n$ dòng. Dòng thứ $i$ mô tả nút $i$ bằng ba giá trị key left right, trong đó left và right là chỉ số con trái và con phải. Chỉ số $0$ biểu thị không có nút con; các chỉ số khác nằm trong $[1,n]$.

Dữ liệu được bảo đảm mô tả một cây nhị phân hợp lệ có gốc $r$: cây liên thông, không có chu trình và mỗi nút khác gốc có đúng một cha. Khóa các nút có thể làm cây vi phạm điều kiện BST.

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, khóa của mỗi nút 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 $5$ có khóa $9$ và nằm trong cây con trái của gốc có khóa $8$. Mọi khóa trong cây con trái của $8$ phải nhỏ hơn $8$, nhưng $9>8$.

Vì vậy cây không phải BST nghiêm ngặt và chương trình in NO.