Trong nhà máy của JOI Co., Ltd. có $N$ chiếc bàn, được đánh số từ $0$ đến $N-1$. Nhà máy có $N-1$ băng chuyền, được đánh số từ $0$ đến $N-2$. Băng chuyền $i$ ($0\le i\le N-2$) nối bàn $A_i$ với bàn $B_i$ và vận chuyển sản phẩm từ một bàn sang bàn còn lại. Tuy nhiên, ta không thể nhìn thấy hướng vận chuyển. Nếu bỏ qua hướng của các băng chuyền, mọi cặp bàn đều được nối với nhau qua một số băng chuyền.

IOI-kun là giám đốc nhà máy. Vì đã quên hướng vận chuyển của mọi băng chuyền, cậu sẽ thực hiện chuỗi thao tác sau nhiều lần.

1. Cậu chọn một số băng chuyền và đảo hướng vận chuyển của các băng chuyền đã chọn.
2. Cậu chọn một số bàn và đặt một sản phẩm lên mỗi bàn đã chọn.

3. Với mỗi bàn có đặt sản phẩm, một trong các tình huống sau xảy ra đồng thời.

   • Nếu không có băng chuyền nào vận chuyển sản phẩm ra khỏi bàn đó, không có gì xảy ra.
   • Nếu có băng chuyền vận chuyển sản phẩm ra khỏi bàn đó, sản phẩm trên bàn được vận chuyển bởi một trong các băng chuyền ấy. Sản phẩm dừng ở bàn đích của băng chuyền và không di chuyển nữa.
4. IOI-kun kiểm tra xem mỗi bàn có ít nhất một sản phẩm hay không. Nếu một bàn có sản phẩm, cậu lấy đi tất cả chúng.
5. Với mỗi băng chuyền đã bị đảo hướng ở thao tác 1, IOI-kun đảo lại hướng của nó. Hướng của nó trở về hướng ban đầu.

IOI-kun muốn xác định hướng ban đầu của mọi băng chuyền bằng cách thực hiện chuỗi thao tác trên nhiều nhất 30 lần.

Hãy viết chương trình, với thông tin về các bàn được nối bởi băng chuyền, cài đặt chiến lược của IOI-kun để xác định hướng ban đầu của mọi băng chuyền bằng cách thực hiện chuỗi thao tác trên nhiều nhất 30 lần.

Chi tiết cài đặt

Bạn cần nộp một tệp.

Tệp đó là conveyor.cpp. Tệp phải cài đặt hàm sau. Chương trình phải đưa conveyor.h vào bằng chỉ thị tiền xử lý #include.

Trong conveyor.cpp, hãy cài đặt hàm sau.

void Solve(int N, std::vector<int> A, std::vector<int> B)

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu kiểm tra.

• Tham số N là số bàn $N$.
• Các tham số A, B là các mảng có độ dài $N-1$, mô tả các bàn được nối bởi băng chuyền.

Chương trình của bạn có thể gọi hàm sau.

std::vector<int> Query(std::vector<int> x, std::vector<int> y)

Bằng hàm này, IOI-kun thực hiện các thao tác trong nhà máy.

• Tham số x là mảng có độ dài $N-1$. Với $0\le i\le N-2$, IOI-kun đảo hướng băng chuyền $i$ nếu x[i] = 1 và không đảo hướng băng chuyền $i$ nếu x[i] = 0.
• Tham số y là mảng có độ dài $N$. Với $0\le j\le N-1$, IOI-kun đặt một sản phẩm lên bàn $j$ nếu y[j] = 1 và không đặt sản phẩm lên bàn $j$ nếu y[j] = 0.
• Gọi z là giá trị trả về của hàm. Đây là mảng có độ dài $N$. Với $0\le j\le N-1$, bàn $j$ có ít nhất một sản phẩm nếu z[j] = 1 và không có sản phẩm nếu z[j] = 0.
• Độ dài mảng x phải bằng $N-1$. Nếu không, chương trình bị chấm là Sai đáp án [1].
• Mọi phần tử của mảng x phải là $0$ hoặc $1$. Nếu không, chương trình bị chấm là Sai đáp án [2].
• Độ dài mảng y phải bằng $N$. Nếu không, chương trình bị chấm là Sai đáp án [3].
• Mọi phần tử của mảng y phải là $0$ hoặc $1$. Nếu không, chương trình bị chấm là Sai đáp án [4].
• Không được gọi Query quá 30 lần. Nếu gọi quá 30 lần, chương trình bị chấm là Sai đáp án [5].

void Answer(std::vector<int> a)

Bằng hàm này, IOI-kun báo cáo hướng ban đầu của mỗi băng chuyền.

• Tham số a là mảng có độ dài $N-1$. Với $0\le i\le N-2$, băng chuyền $i$ vận chuyển sản phẩm từ $A_i$ đến $B_i$ nếu a[i] = 0 và từ $B_i$ đến $A_i$ nếu a[i] = 1.
• Độ dài mảng a phải bằng $N-1$. Nếu không, chương trình bị chấm là Sai đáp án [6].
• Mọi phần tử của mảng a phải là $0$ hoặc $1$. Nếu không, chương trình bị chấm là Sai đáp án [7].
• Nếu IOI-kun báo cáo sai hướng của một băng chuyền, chương trình bị chấm là Sai đáp án [8].
• Phải gọi Answer đúng một lần. Nếu gọi Answer nhiều hơn một lần, chương trình bị chấm là Sai đáp án [9]. Khi Solve kết thúc, nếu chưa gọi Answer, chương trình bị chấm là Sai đáp án [10].

Lưu ý quan trọng

• Chương trình có thể cài đặt các hàm khác để dùng nội bộ hoặc sử dụng biến toàn cục.
• Chương trình không được dùng đầu vào chuẩn và đầu ra chuẩn. Chương trình không được giao tiếp với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, bạn có thể in thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Bạn có thể tải từ trang web kỳ thi một tệp nén chứa trình chấm mẫu để kiểm tra chương trình. Tệp nén cũng chứa một tệp mã nguồn mẫu cho chương trình của bạn.

Trình chấm mẫu là tệp grader.cpp. Để kiểm tra chương trình, đặt grader.cpp, conveyor.cpp, conveyor.h trong cùng một thư mục và chạy lệnh sau để biên dịch. Bạn cũng có thể chạy compile.sh có trong tệp nén.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

Khi biên dịch thành công, tệp thực thi grader được tạo ra.

Lưu ý rằng trình chấm thật khác với trình chấm mẫu. Trình chấm mẫu chạy dưới dạng một tiến trình duy nhất, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào cho trình chấm mẫu

Trình chấm mẫu đọc dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{l} N\\ A_0\ A_1\ \cdots\ A_{N-2}\\ B_0\ B_1\ \cdots\ B_{N-2}\\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$

Với $0\le i\le N-2$, ta có $C_i=0$ nếu băng chuyền $i$ vận chuyển sản phẩm từ bàn $A_i$ đến bàn $B_i$. Ngược lại, $C_i=1$.

Dữ liệu ra của trình chấm mẫu

Trình chấm mẫu in thông tin sau ra đầu ra chuẩn (dấu ngoặc kép chỉ để làm rõ).

• Nếu chương trình được chấm là đúng, trình chấm báo số lần gọi hàm Query theo dạng Accepted: 22.
• Nếu chương trình bị chấm là sai đáp án thuộc bất kỳ loại nào, trình chấm mẫu in loại lỗi đó theo dạng Wrong Answer [4].

Nếu chương trình thỏa mãn điều kiện của nhiều loại lỗi sai đáp án, trình chấm mẫu chỉ báo một trong số đó.

Trong trình chấm mẫu, trong các băng chuyền vận chuyển sản phẩm ra khỏi bàn có đặt sản phẩm, băng chuyền vận chuyển sản phẩm được chọn ngẫu nhiên đều bằng các số giả ngẫu nhiên có kết quả không đổi giữa các lần chạy. Để thay đổi hạt giống sinh số giả ngẫu nhiên, chạy trình chấm mẫu với đối số nguyên đầu tiên như sau.

./grader 2023

Lưu ý về chấm điểm

Với một số bộ dữ liệu kiểm tra, trình chấm thật có tính thích nghi. Điều này nghĩa là trình chấm không có đáp án cố định từ đầu mà phản hồi dựa trên các lần gọi Query trước đó. Đảm bảo tồn tại ít nhất một đáp án không mâu thuẫn với tất cả các phản hồi của trình chấm.

Giới hạn

Mọi dữ liệu vào thỏa mãn các điều kiện sau.

• $0\le A_i\le N-1$ ($0\le i\le N-2$).
• $0\le B_i\le N-1$ ($0\le i\le N-2$).
• Nếu bỏ qua hướng của các băng chuyền, mọi cặp bàn đều được nối với nhau qua một số băng chuyền.

Nhiệm vụ con

1. (1 điểm) $N=2$.
2. (14 điểm) $N=30$.
3. (10 điểm) $N=100\,000$, $A_i=i$ ($0\le i\le N-2$), $B_i=i+1$ ($0\le i\le N-2$).
4. (75 điểm) $N=100\,000$.

Ví dụ về giao tiếp

Dưới đây là một ví dụ dữ liệu vào cho trình chấm mẫu và các lần gọi hàm tương ứng.

Dữ liệu vào 1

3
0 2
2 1
1 0

Các lần gọi hàm mẫu

Với lần gọi Query đầu tiên, ngoài [1, 0, 0], một giá trị trả về khác có thể là [0, 1, 0].

Với lần gọi Query thứ hai, sản phẩm trên bàn $0$ được vận chuyển đến bàn $2$ qua băng chuyền $0$ và dừng ở đó. Lưu ý rằng sản phẩm này sẽ không được vận chuyển đến bàn $1$ qua băng chuyền $1$.

Lưu ý rằng ví dụ dữ liệu vào này không thỏa mãn giới hạn của bất kỳ nhiệm vụ con nào.

Trong các tệp có thể tải từ trang web kỳ thi, sample-02.txt thỏa mãn giới hạn của nhiệm vụ con 1 và sample-03.txt thỏa mãn giới hạn của nhiệm vụ con 2.