Задача №115399. Лягушки на дереве
На ФТ Сириус можно наблюдать не только обыкновенных, но и древесных лягушек, про некоторые виды которых известно, что они могут менять свой цвет с зелёного на коричневый, и наоборот.
Как известно, дерево — это связный граф без циклов. В каждой вершине дерева живёт ровно одна лягушка. Изначально все лягушки имеют зелёный цвет. Лягушки могут прыгать по дереву. За один прыжок лягушка перемещается из вершины дерева, в которой она находится, в соседнюю с ней по ребру вершину. После каждого прыжка цвет лягушки меняется на противоположный.
Лягушки любят петь дуэтом. Дуэт обязательно должен состоять из двух лягушек разного цвета. Чтобы две лягушки образовали дуэт, одна из лягушек должна добраться до вершины, где живет другая лягушка, совершив при этом не более \(d\) прыжков. Чтобы после перемещения цвет гостьи отличался от цвета хозяйки, гостья должна сделать нечётное количество прыжков.
Необходимо определить, какое максимальное количество дуэтов лягушек может образоваться. Каждая лягушка может входить только в один дуэт. Если вы правильно определите максимальное количество дуэтов, вы получите частичный балл за подзадачу. Чтобы получить полный балл за подзадачу необходимо также выяснить, какие пары лягушек должны образовать дуэты, чтобы их оказалось максимальное количество.
Первая строка входных данных содержит одно целое число \(n\) (\(2 \leq n \leq 5\cdot 10^5\)) — количество вершин в дереве.
Вторая строка входных данных содержит одно целое нечётное число \(d\) (\(1 \leq d \leq n - 1\)) — максимальное количество прыжков, которое может сделать одна лягушка на пути к другой.
Каждая из следующих \(n-1\) строк входных данных содержит два целых числа \(u\) и \(v\) (\(1 \leq u, v \leq n\)) — номера вершин дерева, соединённых одним ребром. Вершины пронумерованы от \(1\) до \(n\).
В первой строке выведите одно целое число \(m\) — максимально возможное количество дуэтов лягушек, которые могут образоваться.
Если вы не хотите предъявлять сами пары, то выведите в следующей строке число \(-1\) и завершите работу программы.
Иначе, в следующих \(m\) строках выведите по два целых числа \(u_i\) и \(v_i\) — пару вершин, лягушки из которых должны встретиться в одной из этих вершин и образовать дуэт, соблюдая описанные выше правила.
Если максимальное количество дуэтов может быть образовано несколькими способами, выведите любой из них.
Если решение выводит не максимальное возможное количество пар или некорректный набор пар на одном из тестов подзадачи, то оно получает \(0\) баллов за подзадачу. Если хотя бы на одном тесте подзадачи решение выводит \(-1\) вместо набора пар и на каждом тесте подзадачи выводит либо верный набор пар, либо \(-1\), то оно получает половину баллов за подзадачу. Если на каждом тесте подзадачи решение выводит верный набор пар, то оно получает полный балл за подзадачу.
| Дополнительные ограничения | ||||
| Подзадача | Баллы | \(n\) | \(d\) | Необх. подзадачи |
| 1 | 6 | \(n \le 14\) | – | У |
| 2 | 6 | \(n \le 300\,000\) | \(d=n-1\) | – |
| 3 | 10 | \(n \le 300\,000\) | \(d=1\) | – |
| 4 | 14 | \(n \le 300\,000\) | \(d=3\) | – |
| 5 | 8 | \(n \le 200\) | – | У, 1 |
| 6 | 12 | \(n \le 30\,000\) | \(d \le 9\) | У |
| 7 | 4 | \(n \le 300\,000\) | \(d \le 13\) | У, 1, 3, 4, 6 |
| 8 | 10 | \(n \le 300\,000\) | \(d \le 99\) | У, 1, 3, 4, 6, 7 |
| 9 | 14 | \(n \le 300\,000\) | – | У, 1–8 |
| 10 | 16 | – | – | У, 1–9 |
8 7 1 2 2 3 3 4 3 5 1 6 6 7 3 8
3 2 7 6 3 4 1
11 3 1 2 2 3 3 4 3 5 3 6 3 7 1 8 8 9 8 10 8 11
4 3 7 11 8 10 2 1 6