Каждой твари по паре
Коллекционировать животных можно не только на Ноевом ковчеге, но и на дереве. А дерево, как известно из теории графов, является связным ациклическим графом. Иными словами, дерево состоит из n вершин и n-1 ребра между ними. Каждое ребро соединяет некоторые две вершины дерева. Из любой вершины дерева можно добраться по ребрам до любой другой. Также дерево не содержит циклов, т. е. нельзя построить путь по ребрам из некоторой вершины и вернуться в нее, не пройдя по одному и тому же ребру дважды.
Для расположения животных на нашем дереве сделано q гнезд, где q - четное число. Животным каждого вида предназначены два гнезда.
После расселения по дереву каждая пара одного вида может перемещаться по ребрам дерева между своими гнездами. Они не должны мешать другим видам, т. е. чтобы никакие два пути не имели общего ребра. При этом допускается пересечение путей в вершине. Вам необходимо разместить q/2 видов животных по гнездам таким образом, чтобы пути
животных одного вида удовлетворяли этому условию.
Формат входных данных
В первой строке входных данных находится два целых числа n и q (2≤ n ≤ 2 • 10^5, 2≤n, q четно) — общее количество вершин в дереве и количество вершин, в которых расположены гнезда.
Во второй строке входных данных находятся q различных целых чисел m(i) (1≤ m(i) ≤ n) - номера вершин с гнездами.
В каждой из следующих n - 1 строк входных данных находится два целых u(i) и v(i) ( 1≤ v(i), v(i) ≤ n, u(i)≠v(i) ). Это означает, что между вершинами u(i) и v(i) в дереве проведено ребро.
Гарантируется, что ребра во входных данных образуют дерево.
Формат выходных данных
Выходные данные должны содержать q/2 строк.
В каждой строке должно содержаться два целых числа х(i) и у(i) (1 ≤ x(i), y(i)≤ n) - номера вершин, в которых будут располагаться гнезда i-го вида животных.
Все числа в выходных данных должны быть различны и должны представлять собой номера вершин с гнёздами.
Если разместить животных требуемым образом невозможно, выведите число -1.
Критерии оценивания:
Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру:
1. u(i) = i, v(i) = i+1
2. u(i) = 1, v(i) = i+1
3. n ≤ 3000, q≤6
4. q=n.
5. Нет дополнительных ограничений.
Ввод:
9 6
1 3 2 5 8 6
3 1
3 2
3 4
3 5
3 6
4 7
7 8
1 9
Вывод:
3 2
8 5
1 6
Коллекционировать животных можно не только на Ноевом ковчеге, но и на дереве. А дерево, как известно из теории графов, является связным ациклическим графом. Иными словами, дерево состоит из n вершин и n-1 ребра между ними. Каждое ребро соединяет некоторые две вершины дерева. Из любой вершины дерева можно добраться по ребрам до любой другой. Также дерево не содержит циклов, т. е. нельзя построить путь по ребрам из некоторой вершины и вернуться в нее, не пройдя по одному и тому же ребру дважды.
Для расположения животных на нашем дереве сделано q гнезд, где q - четное число. Животным каждого вида предназначены два гнезда.
После расселения по дереву каждая пара одного вида может перемещаться по ребрам дерева между своими гнездами. Они не должны мешать другим видам, т. е. чтобы никакие два пути не имели общего ребра. При этом допускается пересечение путей в вершине. Вам необходимо разместить q/2 видов животных по гнездам таким образом, чтобы пути
животных одного вида удовлетворяли этому условию.
Формат входных данных
В первой строке входных данных находится два целых числа n и q (2≤ n ≤ 2 • 10^5, 2≤n, q четно) — общее количество вершин в дереве и количество вершин, в которых расположены гнезда.
Во второй строке входных данных находятся q различных целых чисел m(i) (1≤ m(i) ≤ n) - номера вершин с гнездами.
В каждой из следующих n - 1 строк входных данных находится два целых u(i) и v(i) ( 1≤ v(i), v(i) ≤ n, u(i)≠v(i) ). Это означает, что между вершинами u(i) и v(i) в дереве проведено ребро.
Гарантируется, что ребра во входных данных образуют дерево.
Формат выходных данных
Выходные данные должны содержать q/2 строк.
В каждой строке должно содержаться два целых числа х(i) и у(i) (1 ≤ x(i), y(i)≤ n) - номера вершин, в которых будут располагаться гнезда i-го вида животных.
Все числа в выходных данных должны быть различны и должны представлять собой номера вершин с гнёздами.
Если разместить животных требуемым образом невозможно, выведите число -1.
Критерии оценивания:
Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру:
1. u(i) = i, v(i) = i+1
2. u(i) = 1, v(i) = i+1
3. n ≤ 3000, q≤6
4. q=n.
5. Нет дополнительных ограничений.
Ввод:
9 6
1 3 2 5 8 6
3 1
3 2
3 4
3 5
3 6
4 7
7 8
1 9
Вывод:
3 2
8 5
1 6