Codeforces Round 897 (Div. 2) |
---|
Закончено |
Дано дерево с $$$n$$$ вершинами с корнем в вершине $$$1$$$, обозначим его за $$$G$$$. Также обозначим за $$$P(G)$$$ мультимножество поддеревьев всех вершин дерева $$$G$$$. Вам надо найти дерево $$$G'$$$ размера $$$n$$$ с корнем в вершине $$$1$$$ такое, что количество поддеревьев в $$$P(G')$$$ к которым есть изоморфные в $$$P(G)$$$ было минимально.
Поддерево вершины $$$v$$$ - это граф, который содержит все вершины, для которых вершина $$$v$$$ лежит на пути от корня дерева до нее самой, а так же все ребра между этими вершинами.
Два корневых дерева считаются изоморфными если можно так перенумеровать вершины одного из них, чтобы оно стало равно второму, при этом корень первого дерева должен получить номер корня второго дерева.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) - количество вершин в дереве $$$G$$$. Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$a$$$ и $$$b$$$ $$$(1 \leq a,b \leq n)$$$, означающие, что между вершинами $$$a$$$ и $$$b$$$ в дереве есть ребро.
Выведите $$$n-1$$$ строку, каждая строка содержит два числа $$$a$$$, $$$b$$$ $$$(1 \leq a,b \leq n)$$$ - рёбра дерева $$$G'$$$. Если существует несколько оптимальных ответов, выведите любой.
2 1 2
1 2
3 1 2 1 3
1 2 2 3
4 1 2 1 3 3 4
1 2 2 3 3 4
Название |
---|