Đề bài

Nếu từng bộ phận của con tàu Theseus lần lượt được thay thế theo thời gian, thì vào thời điểm nào, nếu có, nó không còn là cùng một con tàu nữa?

Khi không suy ngẫm về những vấn đề trừu tượng, Theseus dành thời gian rảnh để tiêu diệt Minotaur. Tuy nhiên, lần này anh phải đi qua một mê cung tối tăm và ngoằn ngoèo trước. Vì đây không phải việc dễ dàng, Theseus nhờ Ariadne dẫn đường.

Mê cung được biểu diễn bởi một đồ thị vô hướng liên thông gồm \(n\) đỉnh, đánh số từ \(1\) đến \(n\), và \(m\) cạnh. Có một đỉnh đặc biệt \(t\) là nơi Minotaur đang ở.

Theseus hoàn toàn không nhìn thấy đồ thị, còn Ariadne nhìn thấy toàn bộ. Họ sẽ thống nhất một chiến lược để Theseus có thể đến đỉnh chứa Minotaur một cách an toàn: Ariadne gắn nhãn \(0\) hoặc \(1\) lên mỗi cạnh. Sau đó Theseus đi vào mê cung tại một đỉnh \(s\) mà Ariadne không biết trước.

Do mê cung rất tối, tại mỗi thời điểm Theseus chỉ nhìn thấy chỉ số của đỉnh hiện tại, chỉ số của các đỉnh kề và nhãn của các cạnh kề. Hơn nữa, vì mê cung rất ngoằn ngoèo, anh không thể nhớ bất kỳ thông tin nào về những đỉnh đã đi qua trước đó.

Để đến chỗ Minotaur an toàn, Theseus phải thực hiện không quá

bước đi, trong đó \(\operatorname{dist}(s,t)\) là số cạnh ít nhất trên một đường đi từ \(s\) đến \(t\), và \(C\) là một hằng số.

Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau.

std::vector<int> paint(
    int n,
    std::vector<std::pair<int, int>> edges,
    int t
);

• n: số đỉnh của đồ thị.
• edges: danh sách độ dài \(m\) mô tả các cạnh của đồ thị.
• t: đỉnh đích.
• Hàm phải trả về một danh sách độ dài \(m\). Phần tử thứ \(i\) là nhãn của cạnh thứ \(i\) trong edges và phải bằng \(0\) hoặc \(1\).
• Nếu một cạnh được gắn giá trị khác \(0\) và \(1\), hành vi của chương trình không được xác định.
• Hàm được gọi đúng một lần trong mỗi tiến trình tô màu của một bộ kiểm thử.

int travel(
    int n,
    int u,
    std::vector<std::pair<int, int>> neighbours
);

• n: số đỉnh của đồ thị.
• u: đỉnh hiện tại.
• neighbours: danh sách các cặp \((v,e)\), cho biết có một cạnh nối \(u\) với \(v\) và cạnh ấy mang nhãn \(e\).
• Hàm phải trả về một đỉnh kề để Theseus di chuyển tới. Nếu đỉnh trả về là \(t\), chương trình tự động kết thúc.
• Trong mọi lời gọi hàm này, đảm bảo \(u\ne t\).
• Mỗi lời gọi hàm biểu diễn một bước đi trong mê cung. Trong mỗi bộ kiểm thử, hàm có thể được gọi số lần cần thiết cho đến khi Theseus đến đỉnh đích.

Chú ý: Các lời gọi paint và travel được thực hiện trong các tiến trình độc lập. Chương trình không được dùng biến toàn cục hoặc biến static để truyền thông tin giữa các thực thể khác nhau của paint hoặc travel. Mọi hành vi cố lách yêu cầu này đều dẫn đến hành vi không được xác định.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le m\le50\,000\).
• \(C=14\).
• Đỉnh xuất phát \(s\) của mỗi bộ kiểm thử được cố định trước khi gọi hàm label.

Phân nhóm

• Phân nhóm 1 (4 điểm): Đồ thị là một clique, tức là có cạnh giữa mọi cặp đỉnh \(1\le u<v\le n\).
• Phân nhóm 2 (10 điểm): Khoảng cách từ đỉnh đích đến mọi đỉnh trong đồ thị không vượt quá \(2\) cạnh.
• Phân nhóm 3 (11 điểm): Đồ thị là một cây.
• Phân nhóm 4 (13 điểm): Đồ thị là đồ thị hai phía, tức là có thể chia các đỉnh thành hai tập sao cho không có cạnh nối hai đỉnh thuộc cùng một tập.
• Phân nhóm 5 (12 điểm): Đồ thị là một đồ thị bậc thang như định nghĩa dưới đây.
• Phân nhóm 6 (50 điểm): Không có ràng buộc bổ sung.

Đồ thị bậc thang gồm hai đường đi song song có cùng độ dài; mỗi cặp đỉnh tương ứng trên hai đường đi được nối bằng một cạnh để tạo thành các bậc thang. Ở một đầu của bậc thang có đỉnh đặc biệt \(t\), là đỉnh đích, được nối với cả hai đầu mút ở phía đó và đóng vai trò như một đỉnh cha chung. Với mọi đồ thị như vậy, \(n\) luôn là số lẻ.

![Minh họa đồ thị bậc thanghttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_963affdb.png

Ví dụ

Xét đồ thị có \(7\) đỉnh và \(7\) cạnh dưới đây. Đỉnh xuất phát là \(3\), được tô màu xanh lá; đỉnh đích là \(7\), được tô màu đỏ.

![Đồ thị trong ví dụ Theseushttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_388d02c1.png

Đầu tiên, trình chấm gọi paint. Giả sử hàm trả về dãy nhãn sau:

Khi ấy, một chuỗi lời gọi travel hợp lệ đưa Theseus đến đích là:

Khi giá trị trả về là \(7\), tức đỉnh đích, chương trình dừng lại.

Trình chấm mẫu

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

• Dòng \(1\): n m.
• Dòng \(2\): s t.
• Dòng \(3+i\) với \(0\le i<m\): a b, biểu diễn một cạnh nối hai đỉnh \(a\) và \(b\).

Đầu tiên, trình chấm gọi paint với các tham số tương ứng và gắn nhãn cho các cạnh theo danh sách trả về. Sau đó, trình chấm gọi travel với các tham số \(n\), \(s\) và danh sách các đỉnh kề của \(s\). Sau lời gọi đầu tiên, trình chấm tiếp tục gọi travel, lấy đỉnh hiện tại là đỉnh do lời gọi trước trả về, cho đến khi đạt đỉnh đích \(t\).

Với mỗi bước, trình chấm mẫu in đỉnh hiện tại và đỉnh do travel trả về. Cuối cùng, trình chấm in tổng số bước đi.