Anthony là một chú kiến sống ở thành phố JOI. Thành phố có \(N\) thị trấn, đánh số từ \(0\) đến \(N-1\). Anthony sống ở thị trấn \(0\). Có \(M\) con đường, đánh số từ \(0\) đến \(M-1\). Đường thứ \(i\) nối hai thị trấn \(U_i,V_i\) và đi được theo cả hai chiều. Hai con đường khác nhau không nối cùng một cặp thị trấn. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Catherine là một cô mèo, bạn của Anthony. Cô định đến thăm thành phố JOI nhưng không biết thông tin đường sá và thường bị lạc. Anthony quyết định đánh dấu các con đường từ trước. Có \(A\) loại dấu, đánh số từ \(0\) đến \(A-1\).

Catherine đã đến một thị trấn trong thành phố. Mỗi khi ở một thị trấn khác \(0\), với từng loại dấu, cô có thể đếm số đường mang dấu đó đi ra từ thị trấn hiện tại, không tính con đường vừa đi qua nếu có. Sau đó cô chọn một con đường để đi. Ngoại trừ con đường vừa đi qua, cô chỉ phân biệt được các đường dựa trên loại dấu.

Gọi \(d\) là số đường ít nhất cần đi qua để từ thị trấn xuất phát đến thị trấn \(0\). Catherine muốn đến thị trấn \(0\) sau nhiều nhất \(d+B\) lần chọn đường.

Hãy viết chương trình thực hiện chiến lược đánh dấu đường của Anthony khi biết thông tin các con đường, và chương trình thực hiện chiến lược chọn đường của Catherine.

Giao diện giao tiếp

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

Tệp Anthony.cpp thực hiện chiến lược của Anthony, phải khai báo sử dụng Anthony.h và cài đặt hàm:

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V);

Hàm này được gọi đúng một lần lúc bắt đầu.

• \(N\) là số thị trấn; \(M\) là số con đường.
• \(A\) là số loại dấu; \(B\) là số lần chọn đường được phép thêm so với đường đi ngắn nhất.
• U và V là hai mảng dài \(M\); U[i] và V[i] là hai đầu của đường thứ \(i\), với \(0 \le i \le M-1\).
• Giá trị trả về x phải là mảng dài \(M\). Nếu độ dài khác \(M\), bài làm bị chấm Wrong Answer [1].
• x[i] là loại dấu đặt trên đường thứ \(i\), phải thỏa mãn \(0 \le\) x[i] \(\le A-1\). Nếu không, bài làm bị chấm Wrong Answer [2].

Tệp Catherine.cpp thực hiện chiến lược của Catherine, phải khai báo sử dụng Catherine.h và cài đặt hai hàm:

void Init(int A, int B);
int Move(std::vector<int> y);

Hàm Init được gọi đúng một lần lúc bắt đầu. \(A\) là số loại dấu, còn \(B\) là số lần chọn đường được phép thêm so với đường đi ngắn nhất.

Hàm Move được gọi mỗi khi Catherine đến một thị trấn khác \(0\).

• y là mảng dài \(A\). Với \(0 \le j \le A-1\), y[j] là số đường đi ra từ thị trấn hiện tại mang dấu \(j\), không tính đường vừa đi qua nếu có.
• Giá trị trả về \(z\) phải thỏa mãn \(-1 \le z \le A-1\); nếu không, bài làm bị chấm Wrong Answer [3].
• Nếu \(z=-1\), Catherine quay lại theo đường vừa đi qua. Trả về \(-1\) trong lần gọi Move đầu tiên sẽ bị chấm Wrong Answer [4].
• Nếu \(0 \le z \le A-1\), Catherine chọn một đường mang dấu \(z\) trong số các đường được đếm trong y[z]. Nếu y[z] = 0, bài làm bị chấm Wrong Answer [5].

Khi Catherine chọn một đường khác đường vừa đi qua, đường thực tế cô đi sẽ là một trong các đường mang loại dấu đã chỉ định. Việc chọn đường này không nhất thiết là ngẫu nhiên.

Nếu sau \(d+B\) lần đi qua đường, Catherine vẫn chưa đến thị trấn \(0\) (tức là đã gọi Move \(d+B\) lần), bài làm bị chấm Wrong Answer [6].

Có thể cài đặt thêm hàm nội bộ hoặc dùng biến toàn cục. Các tệp nộp được biên dịch cùng trình chấm thành một tệp thực thi. Hãy đặt các hàm nội bộ và biến toàn cục trong namespace không tên để tránh trùng tên với các tệp khác. Khi chấm, Anthony và Catherine chạy trong hai tiến trình riêng, không chia sẻ biến toàn cục.

Chương trình của bạn không được sử dụng đầu vào chuẩn hoặc đầu ra chuẩn, cũng không được giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Trình chấm mẫu

Gói tệp mẫu chứa trình chấm mẫu grader.cpp, các tệp khởi đầu và các tệp tiêu đề. Để dùng trình chấm mẫu, đặt grader.cpp, Anthony.cpp, Catherine.cpp, Anthony.h và Catherine.h trong cùng thư mục.

Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng:

N M A B S
U_0 V_0
...
U_{M-1} V_{M-1}

Ở đây \(S\) là số hiệu thị trấn xuất phát của Catherine.

Dữ liệu ra

Khi kết thúc bình thường, trình chấm mẫu in ra:

• Nếu phát hiện một trong các lỗi Wrong Answer [1] đến Wrong Answer [5], in loại lỗi tương ứng, chẳng hạn Wrong Answer [1].
• Nếu Catherine vẫn chưa đến thị trấn \(0\) sau \(N+B\) lần di chuyển, in Wrong Answer; Number of moves > N + B.
• Ngược lại, in số lần di chuyển (số lần gọi Move), chẳng hạn Number of moves = 4. Trình chấm mẫu không kiểm tra kết quả là đúng hay thuộc lỗi Wrong Answer [6].

Nếu có nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Trong trình chấm mẫu, khi Catherine không quay lại đường vừa đi qua, đường tiếp theo được chọn ngẫu nhiên đều trong số các đường có dấu yêu cầu bằng bộ sinh số giả ngẫu nhiên với hạt giống cố định. Có thể đổi hạt giống bằng đối số nguyên đầu tiên khi chạy trình chấm mẫu, chẳng hạn:

./grader 2020

Ràng buộc

• \(2 \le N \le 20\,000\).
• \(1 \le M \le 20\,000\).
• \(1 \le S \le N-1\), với \(S\) là thị trấn xuất phát của Catherine.
• \(0 \le U_i<V_i \le N-1\) với \(0 \le i \le M-1\).
• \((U_i,V_i)\ne(U_j,V_j)\) với \(0 \le i<j \le M-1\).
• Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(2\) điểm: \(A=4\), \(B=0\), \(M=N-1\)
2. \(2\) điểm: \(A=4\), \(B=0\)
3. \(2\) điểm: \(A=3\), \(B=0\), \(M=N-1\)
4. \(9\) điểm: \(A=3\), \(B=0\)
5. \(5\) điểm: \(A=2\), \(B=2N\), \(M=N-1\), \(6 \le N \le 500\)
6. \(71\) điểm: \(A=2\), \(B=12\), \(M=N-1\)
7. \(9\) điểm: \(A=2\), \(B=6\), \(M=N-1\)

Ví dụ giao tiếp

7 6 2 6 1
0 2
0 4
1 2
1 3
1 5
4 6

Trình chấm mẫu ghi ra:

Number of moves = 4

Đây là một chuỗi lời gọi và giá trị trả về tương ứng với dữ liệu mẫu:

Trong chuỗi giao tiếp này, Catherine lần lượt thăm các thị trấn \(1,5,1,2,0\). Ta có \(d=2\) và Catherine di chuyển \(4\) lần; đầu ra ở trên là kết quả của trình chấm mẫu cho chuỗi giao tiếp này.

Dữ liệu này thỏa mãn ràng buộc của nhóm \(7\). Trong các tệp mẫu được đề gốc nhắc tới, sample-02.txt thỏa mãn ràng buộc của nhóm \(4\).

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 3. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.