N. Nlogônia's Keys
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nlogônia is implementing a new data transmission system between its $$$N$$$ research stations, numbered from $$$1$$$ to $$$N$$$. The network infrastructure is economical: there are exactly $$$N-1$$$ bidirectional cables connecting the stations, so that there is always a single simple path between any pair of stations.

To ensure that messages reach only those who are actually part of the route, the engineers created a mechanism based on access keys:

  1. Each research station will receive a list of access keys.
  2. When a station $$$u$$$ sends a message to another station $$$w$$$, the message is signed with all the keys that $$$u$$$ and $$$w$$$ have in common.
  3. A station $$$v$$$ can only read and authorize the passage of the message if it possesses all the keys used in that signature. If two stations share no key, any station in the network will be able to read the message.

The security committee established the following rules for the distribution of keys:

  • Authorization along the path: Every station $$$v$$$ that lies on the path between $$$u$$$ and $$$w$$$ (including the stations $$$u$$$ and $$$w$$$ themselves) must possess all the keys shared by $$$u$$$ and $$$w$$$.
  • Blocking off the path: If a station $$$v$$$ does not belong to the path between $$$u$$$ and $$$w$$$, there must be at least one key shared by $$$u$$$ and $$$w$$$ that station $$$v$$$ does not possess (preventing it from reading the message).
  • Economy: The global catalog may contain at most $$$2N$$$ distinct key types in the entire network.

Your task is to help the engineering team determine which keys each station should receive in order to satisfy all the requirements.

Input

The first line of input contains a single integer $$$N$$$ ($$$2 \leq N \leq 1000$$$), representing the number of research stations.

The following $$$N-1$$$ lines describe a connection in the network. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq N$$$, $$$u \neq v$$$), indicating that there is a cable directly connecting stations $$$u$$$ and $$$v$$$. It is guaranteed that the network forms a tree.

Output

On the first line, print a single integer $$$K$$$ ($$$0 \leq K \leq 2N$$$), indicating the total number of distinct keys created. The keys are identified by integers from $$$1$$$ to $$$K$$$.

In the next $$$N$$$ lines, print the key list of each station from $$$1$$$ to $$$N$$$. The $$$i$$$-th of these lines must begin with an integer $$$Q_i$$$ ($$$0 \leq Q_i \leq K$$$) indicating the number of keys held by station $$$i$$$, followed by $$$Q_i$$$ distinct integers representing the keys given to station $$$i$$$.

It is guaranteed that at least one valid key assignment exists. If more than one exists, any of them will be accepted.

Example
Input
3
1 2
2 3
Output
4
2 1 3
2 2 3
2 2 4
Note

Explanation for example 1

The network is a line $$$1 - 2 - 3$$$ with $$$N = 3$$$, allowing up to $$$2(3) = 6$$$ keys (the example uses $$$4$$$ keys):

  • Station $$$1$$$ has the keys $$$\{1, 3\}$$$.
  • Station $$$2$$$ has the keys $$$\{2, 3\}$$$.
  • Station $$$3$$$ has the keys $$$\{2, 4\}$$$.

Testing the communications between each pair of stations:

  • Communication between $$$1$$$ and $$$3$$$: The list of common keys is empty. Since the signature contains no keys, station $$$2$$$ is automatically authorized to process the message (and indeed $$$2$$$ belongs to the path between $$$1$$$ and $$$3$$$).
  • Communication between $$$1$$$ and $$$2$$$: The only common key is key $$$3$$$. Station $$$3$$$ does not have key $$$3$$$, so $$$3$$$ is blocked (and indeed $$$3$$$ does not belong to the path between $$$1$$$ and $$$2$$$).
  • Communication between $$$2$$$ and $$$3$$$: The only common key is key $$$2$$$. Station $$$1$$$ does not have key $$$2$$$, so $$$1$$$ is blocked (and indeed $$$1$$$ does not belong to the path between $$$2$$$ and $$$3$$$).