Câu hỏi 111
Trong một đất nước, giữa mỗi cặp thành phố có nhiều nhất một con đường trực tiếp. Giữa hai thành phố bất kì luôn có đường đi (qua một hoặc nhiều con đường) ngay cả sau khi bỏ đi một con đường tùy ý. Ta nói thành phố $A$ có thể được liên thông $k$-định hướng tới thành phố $B$ nếu: ta có thể định hướng nhiều nhất $k$ con đường sao cho sau khi định hướng tùy ý các con đường còn lại, với mỗi con đường $L$ cố định (nối trực tiếp hai thành phố) đều có một đường đi theo chiều định hướng của các con đường, xuất phát từ $A$, đi qua $L$ và kết thúc tại $B$. Giả sử trong một đất nước có $n$ thành phố, hai thành phố bất kì đều có thể được liên thông $k$-định hướng. Giá trị nhỏ nhất của $k$ là bao nhiêu? (Azer Kerimov).