CF468D Tree

Little X has a tree consisting of $ n $ nodes (they are numbered from $ 1 $ to $ n $ ). Each edge of the tree has a positive length. Let's define the distance between two nodes $ v $ and $ u $ (we'll denote it $ d(v,u) $ ) as the sum of the lengths of edges in the shortest path between $ v $ and $ u $ . A permutation $ p $ is a sequence of $ n $ distinct integers $ p_{1},p_{2},...,p_{n} $ $ (1

The first line contains an integer $ n (1

In the first line print the maximum possible value of the described sum. In the second line print $ n $ integers, representing the lexicographically smallest permutation.