CF1819C.The Fox and the Complete Tree Traversal
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The fox Yae climbed the tree of the Sacred Sakura. A tree is a connected undirected graph that does not contain cycles.
The fox uses her magical powers to move around the tree. Yae can jump from vertex v to another vertex u if and only if the distance between these vertices does not exceed 2 . In other words, in one jump Yae can jump from vertex v to vertex u if vertices v and u are connected by an edge, or if there exists such vertex w that vertices v and w are connected by an edge, and also vertices u and w are connected by an edge.
After Yae was able to get the sakura petal, she wondered if there was a cyclic route in the tree v1,v2,…,vn such that:
- the fox can jump from vertex vi to vertex vi+1 ,
- the fox can jump from vertex vn to vertex v1 ,
- all vi are pairwise distinct.
Help the fox determine if the required traversal exists.
输入格式
The first line contains one integer n ( 2≤n≤2⋅105 ) —the number of vertices of the tree.
Each of the following n−1 lines contains two integers u and v ( 1≤u,v≤n , u=v ) — vertices connected by an edge. It is guaranteed that these edges form a tree.
输出格式
On the first line, print "Yes" (without quotes) if the required route of the tree exists, or "No" (without quotes) otherwise.
If the required tree traversal exists, on the second line print n integers of different integers v1,v2,…,vn ( 1≤vi≤n ) — the vertices of the tree in traversal order.
If there are several correct traversals, output any of them.
输入输出样例
输入#1
5 1 2 1 3 3 4 3 5
输出#1
Yes 4 5 1 2 3
输入#2
3 1 2 1 3
输出#2
Yes 1 2 3
输入#3
15 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15
输出#3
No
说明/提示
The tree from the first example is shown below. The bold arrows indicate the fox's route.
In the second example, any sequence of three different vertices is a correct route, because the fox can jump from any vertex to any vertex.
The tree from the third example is shown below. It can be shown that there is no required route for it.