Câu hỏi 21
Ở đất nước hư cấu Mahishmati có $50$ thành phố, trong đó có một thủ đô. Một số cặp thành phố được nối với nhau bởi các chuyến bay hai chiều. Cho một thành phố $A$, một danh sách có thứ tự các thành phố $C_1, \dots, C_{50}$ được gọi là một *phản hành trình* xuất phát từ $A$ nếu
* mọi thành phố (kể cả $A$) xuất hiện trong danh sách đúng một lần, và
* với mỗi $k \in \{1, 2, \dots, 50\}$, không thể đi từ $A$ đến $C_k$ bằng một dãy gồm đúng $k$ chuyến bay (không nhất thiết phân biệt).
Baahubali nhận thấy rằng với mọi thành phố $A$ đều có một phản hành trình xuất phát từ $A$. Hơn nữa, ông có thể đi một dãy các chuyến bay, xuất phát từ thủ đô và đi qua mỗi thành phố đúng một lần. Tìm số nhỏ nhất có thể của tổng số phản hành trình xuất phát từ thủ đô.
* mọi thành phố (kể cả $A$) xuất hiện trong danh sách đúng một lần, và
* với mỗi $k \in \{1, 2, \dots, 50\}$, không thể đi từ $A$ đến $C_k$ bằng một dãy gồm đúng $k$ chuyến bay (không nhất thiết phân biệt).
Baahubali nhận thấy rằng với mọi thành phố $A$ đều có một phản hành trình xuất phát từ $A$. Hơn nữa, ông có thể đi một dãy các chuyến bay, xuất phát từ thủ đô và đi qua mỗi thành phố đúng một lần. Tìm số nhỏ nhất có thể của tổng số phản hành trình xuất phát từ thủ đô.