Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Дано некорневое дерево с $n$ вершинами. Вам нужно присвоить каждой вершине различный вес так, чтобы веса образовывали перестановку чисел от $1$ до $n$.

Для любой схемы присвоения весов рассмотрим все диаметры дерева (то есть самые длинные простые пути в дереве). Среди этих диаметров выберем тот, у которого лексикографически наибольшая последовательность весов (выписывая веса вершин вдоль пути по порядку и сравнивая их лексикографически).

Ваша цель — минимизировать лексикографический порядок последовательности весов, соответствующей этому «лексикографически наибольшему диаметру», среди всех возможных схем присвоения весов.

Входные данные

Один тест содержит несколько групп данных.

В первой строке входных данных записано количество групп данных $T$ ($1 \le T \le 10^5$), представляющее число групп данных в этом тесте.

Для каждой группы данных первая строка содержит целое число $n$ ($2 \le n \le 2 \cdot 10^5$), указывающее количество вершин.

Следующие $n - 1$ строк содержат по два целых числа $u, v$ ($1 \le u, v \le n$), обозначающих ребро дерева.

Гарантируется, что по всем наборам данных $\sum n \le 2 \cdot 10^5$.

Выходные данные

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

Пример

Входные данные

5
5
1 2
1 3
2 4
2 5
4
1 2
1 3
1 4
6
1 2
1 3
2 4
2 5
3 6
8
1 2
2 3
1 4
2 5
3 6
1 7
7 8
10
1 2
2 3
2 4
4 7
4 8
1 5
5 6
6 9
1 10

Выходные данные

3 4 5 1
3 4 2
3 4 5 6 1
2 3 4 5 6 1
3 4 5 6 7 8 1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.