Problem: In Berland there are n cities and n - 1 bidirectional roads. Each road connects some pair of cities, from any city you can get to any other one using only the given roads.

In each city there is exactly one repair brigade. To repair some road, you need two teams based in the cities connected by the road to work simultaneously for one day. Both brigades repair one road for the whole day and cannot take part in repairing other roads on that day. But the repair brigade can do nothing on that day.

Determine the minimum number of days needed to repair all the roads. The brigades cannot change the cities where they initially are.

Input

The first line of the input contains a positive integer n (2 ≤ n ≤ 200 000) — the number of cities in Berland.

Each of the next n - 1 lines contains two numbers ui, vi, meaning that the i-th road connects city ui and city vi (1 ≤ ui, vi ≤ n, ui ≠ vi).

Output

First print number k — the minimum number of days needed to repair all the roads in Berland.

In next k lines print the description of the roads that should be repaired on each of the k days. On the i-th line print first number di — the number of roads that should be repaired on the i-th day, and then di space-separated integers — the numbers of the roads that should be repaired on the i-th day. The roads are numbered according to the order in the input, starting from one.

If there are multiple variants, you can print any of them.

Examples

Input

4
1 2
3 4
3 2


Output

2
2 2 1
1 3


Input

6
3 4
5 4
3 2
1 3
4 6


Output

3
1 1 
2 2 3 
2 4 5 

Note

In the first sample you can repair all the roads in two days, for example, if you repair roads 1 and 2 on the first day and road 3 — on the second day.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Alex
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
    static class TaskC {
        void dfs(int cur, int parent, int incr, ArrayList<IntIntPair>[] adj, ArrayList<Integer>[] res) {
            int count = 0;
            for(IntIntPair nxt : adj[cur])
                if(nxt.first != parent) {
                    if(count == incr) count++;
                    res[count].add(nxt.second);
                    dfs(nxt.first, cur, count, adj, res);
                    count++;
                }
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int[] as = new int[n - 1], bs = new int[n - 1];
            IOUtils.readIntArrays(in, as, bs);
            MiscUtils.decreaseByOne(as, bs);
            ArrayList<IntIntPair>[] adj = new ArrayList[n];
            for(int i = 0; i < adj.length; i++)
                adj[i] = new ArrayList<>();
            for(int i = 0; i < n - 1; i++) {
                adj[as[i]].add(new IntIntPair(bs[i], i + 1));
                adj[bs[i]].add(new IntIntPair(as[i], i + 1));
            }
            int[] degree = new int[n];
            for(int i = 0; i < n - 1; i++) {
                degree[as[i]]++;
                degree[bs[i]]++;
            }
            int maxdegree = ArrayUtils.maxElement(degree);
            out.printLine(maxdegree);
            ArrayList<Integer>[] res = new ArrayList[maxdegree];
            for(int i = 0; i < res.length; i++)
                res[i] = new ArrayList<>();
            dfs(0, -1, -1, adj, res);
            for(ArrayList<Integer> al : res) {
                out.print(al.size() + " ");
                for(int val : al)
                    out.print(val + " ");
                out.printLine();
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for(int i = 0; i < objects.length; i++) {
                if(i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine() {
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if(numChars == -1)
                throw new InputMismatchException();
            if(curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch(IOException e) {
                    throw new InputMismatchException();
                }
                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while(isSpaceChar(c))
                c = read();
            int sgn = 1;
            if(c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if(c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while(!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if(filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static abstract class IntAbstractStream implements IntStream {

        public String toString() {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for(IntIterator it = intIterator(); it.isValid(); it.advance()) {
                if(first) {
                    first = false;
                } else {
                    builder.append(' ');
                }
                builder.append(it.value());
            }
            return builder.toString();
        }


        public boolean equals(Object o) {
            if(!(o instanceof IntStream)) {
                return false;
            }
            IntStream c = (IntStream) o;
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while(it.isValid() && jt.isValid()) {
                if(it.value() != jt.value()) {
                    return false;
                }
                it.advance();
                jt.advance();
            }
            return !it.isValid() && !jt.isValid();
        }


        public int hashCode() {
            int result = 0;
            for(IntIterator it = intIterator(); it.isValid(); it.advance()) {
                result *= 31;
                result += it.value();
            }
            return result;
        }

    }

    static interface IntCollection extends IntStream {
        public int size();

    }

    static class IntIntPair implements Comparable<IntIntPair> {
        public final int first;
        public final int second;

        public IntIntPair(int first, int second) {
            this.first = first;
            this.second = second;
        }


        public boolean equals(Object o) {
            if(this == o) return true;
            if(o == null || getClass() != o.getClass()) return false;

            IntIntPair pair = (IntIntPair) o;

            return first == pair.first && second == pair.second;

        }


        public int hashCode() {
            int result = Integer.hashCode(first);
            result = 31 * result + Integer.hashCode(second);
            return result;
        }


        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({"unchecked"})
        public int compareTo(IntIntPair o) {
            int value = Integer.compare(first, o.first);
            if(value != 0) {
                return value;
            }
            return Integer.compare(second, o.second);
        }

    }

    static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
        public IntIterator intIterator();

        default public Iterator<Integer> iterator() {
            return new Iterator<Integer>() {
                private IntIterator it = intIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Integer next() {
                    int result = it.value();
                    it.advance();
                    return result;
                }
            };
        }

        default public int compareTo(IntStream c) {
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while(it.isValid() && jt.isValid()) {
                int i = it.value();
                int j = jt.value();
                if(i < j) {
                    return -1;
                } else if(i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if(it.isValid()) {
                return 1;
            }
            if(jt.isValid()) {
                return -1;
            }
            return 0;
        }

        default public int max() {
            int result = Integer.MIN_VALUE;
            for(IntIterator it = intIterator(); it.isValid(); it.advance()) {
                int current = it.value();
                if(current > result) {
                    result = current;
                }
            }
            return result;
        }

    }

    static class MiscUtils {
        public static void decreaseByOne(int[]... arrays) {
            for(int[] array : arrays) {
                for(int i = 0; i < array.length; i++)
                    array[i]--;
            }
        }

    }

    static class IntArray extends IntAbstractStream implements IntList {
        private int[] data;

        public IntArray(int[] arr) {
            data = arr;
        }

        public int size() {
            return data.length;
        }

        public int get(int at) {
            return data[at];
        }

        public void removeAt(int index) {
            throw new UnsupportedOperationException();
        }

    }

    static interface IntList extends IntReversableCollection {
        public abstract int get(int index);

        public abstract void removeAt(int index);

        default public IntIterator intIterator() {
            return new IntIterator() {
                private int at;
                private boolean removed;

                public int value() {
                    if(removed) {
                        throw new IllegalStateException();
                    }
                    return get(at);
                }

                public boolean advance() {
                    at++;
                    removed = false;
                    return isValid();
                }

                public boolean isValid() {
                    return !removed && at < size();
                }

                public void remove() {
                    removeAt(at);
                    at--;
                    removed = true;
                }
            };
        }

    }

    static interface IntReversableCollection extends IntCollection {
    }

    static class ArrayUtils {
        public static int maxElement(int[] array) {
            return new IntArray(array).max();
        }

    }

    static class IOUtils {
        public static void readIntArrays(InputReader in, int[]... arrays) {
            for(int i = 0; i < arrays[0].length; i++) {
                for(int j = 0; j < arrays.length; j++)
                    arrays[j][i] = in.readInt();
            }
        }

    }

    static interface IntIterator {
        public int value() throws NoSuchElementException;

        public boolean advance();

        public boolean isValid();

    }
}