Problem: This problem is split into two tasks. In this task, you are required to find the minimum possible answer. In the task Village (Maximum) you are required to find the maximum possible answer. Each task is worth 50 points.

There are N houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly 1 kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are N-1 roads in the village.

One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the smallest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers.

<image>

Example village with seven houses 

For example, if there are seven houses connected by roads as shown on the figure, the smallest total length is 8 km (this can be achieved by moving 1 → 6, 2 → 4, 3 → 1, 4 → 2, 5 → 7, 6 → 3, 7 → 5).

Write a program that finds the smallest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

Input

The first line contains an integer N (1 < N ≤ 10^5). Houses are numbered by consecutive integers 1, 2, …, N.

Then N-1 lines follow that describe the roads. Each line contains two integers a and b (1 ≤ a, b ≤ N, a ≠ b) denoting that there is a road connecting houses a and b.

Output

In the first line output the smallest total length of the shortest paths in kilometers.

In the second line describe one valid assignment of the new houses with the smallest total length: N space-separated distinct integers v_1, v_2, …, v_N. For each i, v_i is the house number where the villager from the house i should move (v_i ≠ i). If there are several valid assignments, output any of those.

Scoring

Subtasks: 

  1. (6 points) N ≤ 10 
  2. (19 points) N ≤ 1 000 
  3. (25 points) No further constraints 

Examples

Input


4
1 2
2 3
3 4


Output


4
2 1 4 3


Input


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


Output


8
3 4 6 2 7 1 5

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 *
 * @author pttrung
 */
public class B1_Baltic_2020_Day2 {
    public static long MOD = 1000000007;
    static ArrayList<Integer>[] store;
    static int result = 0;


    public static void main(String[] args) throws FileNotFoundException {
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
        // "output.txt")));
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();
        int n = in.nextInt();
        ArrayList<Integer>[] map = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            map[u].add(v);
            map[v].add(u);
        }
        if (n == 2) {
            out.println(2);
            out.println(2 + " " + 1);
        } else {
            store = new ArrayList[n];
            int[] re = new int[n];
            int v = cal(0, 0, re, map);
            if (v != -1) {
                for (int index : map[v]) {
                    result += 2;
                    store[index].add(v);
                    int last = index;
                    for (int i : store[index]) {
                        re[i] = last;
                        last = i;
                    }
                    re[index] = last;
                    break;
                }
            }
            out.println(result);
            for (int i : re) {
                out.print((i + 1) + " ");
            }
        }

        out.close();
    }

    static int cal(int index, int pa, int[] re, ArrayList<Integer>[] map) {
        store[index] = new ArrayList<>();
        for (int i : map[index]) {
            if (i == pa) {
                continue;
            }
            int v = cal(i, index, re, map);
            if (v != -1) {
                store[index].add(v);
            }
        }
        if (store[index].isEmpty()) {
            return index;
        } else {
            result += 2 * (1 + store[index].size()) - 2;
            int last = index;
            for (int i : store[index]) {
                re[i] = last;
                last = i;
            }
            re[index] = last;
            return -1;
        }
    }


    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;

    }

    public static class Point implements Comparable<Point> {

        int x, y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 47 * hash + this.x;
            hash = 47 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(x, o.x);
        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }

        long val = pow(a, b / 2);
        if (b % 2 == 0) {
            return val * val;
        } else {
            return val * (val * a);

        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //  br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}