n вершин с номерами от 1 до n; связи перечислены в links, каждая — пара [a, b]. Граф может быть несвязным.
Вершины нужно разложить по слоям, пронумерованным 1, 2, …, m, так чтобы:
- каждая вершина оказалась ровно в одном слое;
- для любой связи [a, b] номера слоёв вершин a и b отличались ровно на 1.
Верните наибольшее возможное число слоёв m, или -1, если разложить вершины так нельзя.n=5, links=[[1, 2], [2, 3], [3, 4], [2, 5]] → 4
Слои: {1}, {2}, {3, 5}, {4} — каждая связь соединяет соседние слои. Пятый слой не получится: самый длинный кратчайший путь в графе (от 1 до 4) проходит через 4 вершины.
n=4, links=[[1, 2], [2, 3], [3, 1]] → -1
Треугольник 1–2–3: связанные вершины должны лежать в соседних слоях, а у трёх попарно соседних вершин так не выйдет. Ответ -1.
n=4, links=[[1, 2], [3, 4]] → 4
Две отдельные пары: каждая даёт по два слоя, вместе 4.
n=5, links=[[1, 2], [2, 3], [3, 4], [2, 5]]
4
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 85 тестов на сервере, включая скрытые.