Búp bê cơ khí là một con búp bê tự động lặp đi lặp lại một dãy các cử động nhất định. Ở Nhật Bản, có nhiều loại búp bê cơ khí được tạo từ thời xưa.

Các cử động của búp bê cơ khí được điều khiển bởi một mạch bao gồm nhiều thiết bị. Các thiết bị được nối với nhau bởi các đường ống. Mỗi thiết bị có một hoặc hai đầu ra, và có thể có một số lượng tùy ý (có thể là không) đầu vào. Mỗi đường ống nối một đầu ra của một thiết bị với một đầu vào của chính thiết bị đó hoặc của một thiết bị khác. Chính xác một đường ống được nối với mỗi đầu vào, và chính xác một đường ống được nối với mỗi đầu ra.

Để mô tả cách một con búp bê thực hiện các cử động, xét một quả bóng được đặt tại một trong các thiết bị. Quả bóng di chuyển trong mạch. Tại mỗi bước, quả bóng rời thiết bị qua một trong các đầu ra của thiết bị, di chuyển theo đường ống nối đến đầu ra và đi vào thiết bị tại đầu kia của đường ống.

Có ba kiểu thiết bị: nguồn (origin), kích hoạt (trigger) và chuyển đổi (switch). Có đúng một thiết bị nguồn, \(M\) thiết bị kích hoạt và \(S\) thiết bị chuyển đổi (\(S\) có thể bằng không). Bạn phải xác định giá trị của \(S\). Mỗi thiết bị có một số hiệu duy nhất.

Thiết bị nguồn là thiết bị nơi đầu tiên quả bóng được đặt vào. Thiết bị nguồn có một đầu ra. Số hiệu của nó là \(0\).

Một thiết bị kích hoạt sẽ điều khiển búp bê thực hiện một cử động cụ thể khi quả bóng đi vào nó. Mỗi thiết bị kích hoạt có một đầu ra. Số hiệu của các thiết bị kích hoạt là từ \(1\) đến \(M\).

Mỗi thiết bị chuyển đổi có hai đầu ra được gọi là X và Y. Trạng thái của một thiết bị chuyển đổi hoặc là X hoặc là Y. Sau khi quả bóng đi vào một thiết bị chuyển đổi, nó rời thiết bị bằng đầu ra được xác định bởi trạng thái hiện tại của thiết bị. Sau đó, thiết bị chuyển đổi chuyển trạng thái của nó sang trạng thái đối lại. Ban đầu, trạng thái của tất cả các thiết bị chuyển đổi là X. Số hiệu của các thiết bị chuyển đổi là từ \(-1\) đến \(-S\).

Bạn được cho số lượng thiết bị kích hoạt \(M\). Bạn cũng được cho một dãy \(A\) có độ dài \(N\), mỗi phần tử là số hiệu của một thiết bị kích hoạt. Mỗi thiết bị kích hoạt có thể xuất hiện một vài (có thể không) lần trong dãy \(A\). Nhiệm vụ của bạn là tạo ra một mạch thỏa mãn các điều kiện sau:

• Quả bóng quay lại thiết bị nguồn sau một số bước nào đó.
• Khi quả bóng quay lại thiết bị nguồn lần đầu tiên, trạng thái của mỗi thiết bị chuyển đổi là X.
• Quả bóng quay lại thiết bị nguồn lần đầu tiên sau khi đi vào các thiết bị kích hoạt đúng \(N\) lần. Số hiệu của các thiết bị kích hoạt, theo thứ tự mà quả bóng đi vào, là \(A_0, A_1, \ldots, A_{N-1}\).
• Gọi \(P\) là tổng số lần thay đổi trạng thái của tất cả các thiết bị chuyển đổi do quả bóng gây ra trước khi nó quay lại thiết bị nguồn lần đầu tiên. Giá trị của \(P\) không được vượt quá \(20\,000\,000\).

Đồng thời, bạn không muốn sử dụng quá nhiều thiết bị chuyển đổi.

Chi tiết cài đặt

Bạn phải cài đặt thủ tục sau, với chữ ký C++ trong tệp doll.h của gói đính kèm:

void create_circuit(int M, std::vector<int> A);

• M: số lượng thiết bị kích hoạt.
• A: mảng độ dài \(N\), cho biết số hiệu của các thiết bị kích hoạt theo thứ tự mà quả bóng cần đi vào.
• Thủ tục này được gọi đúng một lần.
• Lưu ý, giá trị \(N\) là độ dài của mảng A, và có thể lấy được theo cách mô tả trong Lưu ý cài đặt.

Chương trình của bạn phải gọi thủ tục sau để trả lời:

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

• C: mảng độ dài \(M+1\). Đầu ra của thiết bị \(i\) (\(0 \le i \le M\)) được nối với thiết bị C[i].
• X, Y: các mảng cùng độ dài. Độ dài \(S\) của các mảng này là số lượng thiết bị chuyển đổi. Với thiết bị chuyển đổi \(-j\) (\(1 \le j \le S\)), đầu ra X được nối với thiết bị X[j - 1] và đầu ra Y được nối với thiết bị Y[j - 1].
• Mọi phần tử của C, X và Y phải là số nguyên nằm giữa \(-S\) và \(M\), bao gồm cả hai đầu mút.
• \(S\) nhiều nhất là \(400\,000\).
• Thủ tục này phải được gọi đúng một lần.
• Mạch được biểu diễn bởi C, X và Y phải thỏa mãn các điều kiện trong phát biểu bài toán.

Nếu một trong các điều kiện nêu trên không được thỏa mãn, chương trình của bạn được chấm là Wrong Answer. Ngược lại, chương trình được chấm là Accepted và điểm của bạn được tính theo \(S\) (xem phần Subtasks).

Ví dụ

Cho \(M=4\), \(N=4\) và \(A=[1,2,1,3]\). Trình chấm gọi create_circuit(4, [1, 2, 1, 3]).

Hình trên biểu diễn một mạch được mô tả bằng lời gọi answer([1, -1, -2, 0, 2], [2, -2], [3, 1]). Các con số trong hình là số hiệu của các thiết bị.

Có hai thiết bị chuyển đổi được sử dụng. Do đó, \(S=2\). Ban đầu, trạng thái của cả hai thiết bị chuyển đổi \(-1\) và \(-2\) là X.

Quả bóng di chuyển như sau:

• Khi quả bóng lần đầu tiên đi vào thiết bị chuyển đổi \(-1\), trạng thái của nó là X. Do đó, quả bóng di chuyển tới thiết bị kích hoạt \(2\). Tiếp theo, trạng thái của thiết bị chuyển đổi \(-1\) được chuyển thành Y.
• Khi quả bóng đi vào thiết bị chuyển đổi \(-1\) lần thứ hai, trạng thái của nó là Y. Do đó, quả bóng di chuyển tới thiết bị kích hoạt \(3\). Tiếp theo, trạng thái của thiết bị chuyển đổi \(-1\) được chuyển thành X.

Khi quả bóng quay lại thiết bị nguồn lần đầu tiên, nó đã đi vào các thiết bị kích hoạt \(1,2,1,3\). Trạng thái của cả hai thiết bị chuyển đổi \(-1\) và \(-2\) là X. Giá trị của \(P\) là \(4\). Vì vậy, mạch thỏa mãn các điều kiện.

Tệp sample-01-in.txt trong gói nén đính kèm tương ứng với ví dụ này. Dữ liệu đầu vào của các ví dụ khác cũng có trong gói đính kèm.

Hạn chế

• \(1 \le M \le 100\,000\).
• \(1 \le N \le 200\,000\).
• \(1 \le A_k \le M\) (\(0 \le k \le N-1\)).

Phân nhóm

Điểm và các hạn chế cho mỗi bộ dữ liệu như sau:

Với mỗi bộ dữ liệu, nếu chương trình của bạn được chấm là Accepted, điểm của bạn được tính dựa vào giá trị \(S\):

• Nếu \(S \le N+\log_2 N\), bạn đạt toàn bộ số điểm của bộ dữ liệu.
• Với mỗi bộ dữ liệu trong subtasks \(5\) và \(6\), nếu \(N+\log_2 N < S \le 2N\), bạn đạt một phần điểm. Điểm của bộ dữ liệu bằng hệ số dưới đây nhân với số điểm được cho của subtask:

• Trong các trường hợp còn lại, điểm là \(0\).

Điểm của bạn cho mỗi subtask là điểm nhỏ nhất của các bộ dữ liệu trong subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu từ thiết bị vào chuẩn theo khuôn mẫu sau:

• Dòng \(1\): \(M\ N\).
• Dòng \(2\): \(A_0\ A_1\ \ldots\ A_{N-1}\).

Trình chấm mẫu xuất ba dữ liệu ra.

Đầu tiên, trình chấm mẫu đưa câu trả lời của bạn ra tệp out.txt theo khuôn mẫu sau:

• Dòng \(1\): \(S\).
• Dòng \(2+i\) (\(0 \le i \le M\)): C[i].
• Dòng \(2+M+j\) (\(1 \le j \le S\)): X[j - 1] Y[j - 1].

Thứ hai, trình chấm mẫu mô phỏng các bước di chuyển của quả bóng. Nó đưa số hiệu của các thiết bị quả bóng đi vào, theo thứ tự, ra tệp log.txt.

Thứ ba, trình chấm mẫu in đánh giá kết quả của bạn ra thiết bị ra chuẩn. Nếu chương trình của bạn được chấm là Accepted, trình chấm mẫu in \(S\) và \(P\) theo khuôn mẫu Accepted: S P. Nếu chương trình được chấm là Wrong Answer, nó in Wrong Answer: MSG, trong đó ý nghĩa của MSG như sau:

Lưu ý, trình chấm mẫu có thể không tạo ra out.txt và/hoặc log.txt khi chương trình của bạn được chấm là Wrong Answer.

Dữ liệu vào của ví dụ trên:

4 4
1 2 1 3

Với mạch được mô tả trong ví dụ, dòng đánh giá trên thiết bị ra chuẩn là:

Accepted: 2 4