Даже если вы просто оставите их в покое, они разлетятся на куски сами по себе. Значит, кто-то должен их защищать, верно?

Вы снова играете с Тьюсером в городе Лиюэ. Водя эксцентричного малыша по городу, вы заметили кое-что интересное в его структуре.

Лиюэ можно представить в виде направленного графа, содержащего $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$. Ребро из вершины $$$a$$$ в вершину $$$b$$$ существует тогда и только тогда, когда $$$a < b$$$.

Путь между вершинами $$$a$$$ и $$$b$$$ определяется как последовательность ребер таких, можно начать путь в $$$a$$$, пройти по всем этим ребрам в соответствующем неправлении, и закончить в $$$b$$$. Длина пути равна количеству ребер. Радужный путь длины $$$x$$$ определяется как такой путь в графе, что среди этих $$$x$$$ ребер существует по крайней мере 2 разных цвета.

Любимое число Тьюсера — $$$k$$$. Вам интересно следующее: если вам нужно обозначить каждое ребро цветом, то какое минимальное количество цветов понадобится для того, чтобы все пути длины $$$k$$$ или больше были радужными?

Тьюсер хочет удивить своего старшего брата картой Лиюэ. Он также хочет узнать допустимую раскраску ребер, которая использует минимальное количество цветов. Пожалуйста, помогите ему решить эту задачу!