Những cây gạo nơi quê nhà vẫn sống trong ký ức ngày một nhạt nhòa của 小 N. Ký ức của 小 N về quê nhà có thể được biểu diễn bằng một dãy có độ dài $n$: $[a_0,a_1,\ldots,a_{n-1}]$.

Mỗi cây gạo nơi quê nhà đều có dạng một cây không gốc với các đỉnh được đánh số. Ấn tượng của 小 N về một cây gạo có thể được mô tả bằng một đoạn $[l,r)$ trong ký ức quê nhà của cô:

• Cây có $k=r-l+2$ đỉnh, được đánh số từ $0\sim k-1$.
• $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$ là mã Prüfer của cây này; định nghĩa mã Prüfer được trình bày chi tiết trong phần Ghi chú.

Khi nhớ lại chuyện xưa, 小 N cũng đặt cho bạn $m$ truy vấn. Truy vấn thứ $i$ ($0\le i<m$) là:

• Trên cây gạo tương ứng với đoạn $[l_i,r_i)$ của ký ức quê nhà, hai đỉnh $x_i,y_i$ có kề nhau không?

Chi tiết cài đặt

Thí sinh không cần và cũng không được cài đặt hàm main.

Thí sinh cần bảo đảm tệp mã nguồn nộp bài chứa tệp tiêu đề kapok.h, tức là thêm đoạn mã sau vào đầu chương trình:

#include "kapok.h"

Thí sinh cần cài đặt hàm sau trong tệp mã nguồn nộp bài kapok.cpp:

std::vector<bool> kapok(int c, int n, int m,
std::vector<int> a, std::vector<int> l, std::vector<int>
r, std::vector<int> x, std::vector<int> y);

• $c,n,m$ lần lượt biểu thị số hiệu bộ kiểm thử, độ dài dãy ký ức quê nhà và số truy vấn; $c=0$ biểu thị bộ kiểm thử này là ví dụ.
• a biểu thị dãy ký ức quê nhà.
• l, r lần lượt biểu thị hai đầu mút của đoạn được cho trong mỗi truy vấn.
• x, y lần lượt biểu thị số hiệu của hai đỉnh được cho trong mỗi truy vấn.
• Hàm cần trả về một dãy $f_0,f_1,\ldots,f_{m-1}$ có độ dài đúng bằng $m$, trong đó $f_i$ ($0\le i<m$) biểu thị kết quả của truy vấn thứ $i$.
• Với mỗi bộ kiểm thử, hàm sẽ được chương trình chấm gọi đúng một lần.

Tệp template_kapok.cpp trong thư mục bài này là mã ví dụ được cung cấp; thí sinh có thể tham khảo và cài đặt mã của mình.

Cách kiểm thử chương trình

Thí sinh có thể dùng lệnh sau trong thư mục bài này để biên dịch thành tệp thực thi:

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

Với tệp thực thi kapok đã biên dịch:

• Tệp thực thi đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

  • Dòng đầu tiên chứa ba số nguyên không âm $c,n,m$.
  • Dòng thứ hai chứa $n$ số nguyên không âm $a_0,a_1,\ldots,a_{n-1}$.
  • Dòng thứ $i+3$ ($0\le i<m$) chứa bốn số nguyên không âm $l_i,r_i,x_i,y_i$.

• Tệp thực thi ghi dữ liệu ra đầu ra chuẩn theo định dạng sau:

  • Dòng thứ $i+1$ ($0\le i<m$) chứa một số nguyên không âm, trong đó $0$ biểu thị $f_i$ là false, $1$ biểu thị $f_i$ là true.

Ví dụ

Dữ liệu vào 1

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

Dữ liệu ra 1

1
0
1

Ghi chú

• Cây tương ứng với đoạn $[0,3)$ có $5$ đỉnh, mã Prüfer là $[2,0,2]$, tập cạnh là $\{(1,2),(0,3),(0,2),(2,4)\}$, nên hai đỉnh $0,2$ kề nhau.
• Cây tương ứng với đoạn $[3,5)$ có $4$ đỉnh, mã Prüfer là $[3,0]$, tập cạnh là $\{(1,3),(0,2),(0,3)\}$, nên hai đỉnh $1,2$ không kề nhau.
• Cây tương ứng với đoạn $[0,0)$ có $2$ đỉnh, mã Prüfer rỗng, cạnh duy nhất là $(0,1)$, nên hai đỉnh $0,1$ kề nhau.

Ví dụ 2

Xem các tệp kapok/kapok2.in và kapok/kapok2.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn các ràng buộc của các bộ kiểm thử $3\sim 5$.

Ví dụ 3

Xem các tệp kapok/kapok3.in và kapok/kapok3.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn các ràng buộc của các bộ kiểm thử $3\sim 5$.

Giới hạn

Với mọi dữ liệu kiểm thử:

• $1\le n,m\le 2\times 10^5$.
• Với mọi $0\le i<n$, $0\le a_i<n+2$.
• Với mọi $0\le i<m$, $0\le l_i\le r_i\le n$ và $0\le x_i,y_i<r_i-l_i+2$.

• Tính chất đặc biệt A: với mọi $0\le i<m$, sau khi cho $l_i,r_i$, cặp $x_i,y_i$ được sinh ngẫu nhiên độc lập và đều từ mọi cặp đỉnh có thứ tự thỏa mãn các giới hạn.

Ghi chú

Với một cây không gốc $T$ có các đỉnh được đánh số từ $0\sim c-1$ ($c\ge 2$):

• Lần lượt thực hiện $c-2$ thao tác, trong đó thao tác thứ $i$ ($0\le i<c-2$) như sau:

  • Tìm lá $v_i$ có số hiệu nhỏ nhất hiện tại.
  • Ghi lại số hiệu $p_i$ của đỉnh kề duy nhất của nó.
  • Sau đó xóa $v_i$ và cạnh kề duy nhất của nó khỏi $T$.

• Dãy $[p_0,p_1,\ldots,p_{c-3}]$ có độ dài $c-2$ thu được chính là mã Prüfer của $T$.