This is an approximate problem.

Let's define tree $T_K$ in the following way:

1. $T_1$ is a tree with just one vertrex.

2. If $K>1$ then let $D$ be the biggest integer such that $D | K$ and $1 \le D < K$. The tree $T_K$ will be the union of $T_{K - 1}$ with vertex $\{ K \}$ and edge $(D,K)$.

The image below represents the tree $T_8$.

Two graphs $G_1 = (\{ A_1, A_2, \dots, A_M \}, E_1) \ \& \ G_2 = (\{ B_1, B_2, \dots, B_M \}, E_2)$ are isomorphic if there exists a permutation $P$ of length $M$ such that $\forall$ $(i,j)$, $(A_i,A_j) \in E_1 \iff (B_{P_i},B_{P_j}) \in E_2$.

Given a tree $F$ with $N$ vertices. Let $E$ be the set of edges. You need to delete some edges from the tree, such for every disjoint tree $U$ in the remaining forest there exists an integer $i$ such that $U$ is isomorphic to $T_i$.

Input

The first line contains two integers - $N$, $W$.

The following $N - 1$ lines contain two integers - $U, V$, meaning there is edge $(U,V)$ in tree $F$.

Scoring

Suppose the sizes of the trees in the remaining forest are $S_1, S_2, \dots, S_L$. Let $R = \frac{\sum_{i = 1}^{L} S_i^3}{W}$, then your score will be equal to $10000^{\min(1.25,R)} + max(0,R - 1.25) \cdot 10$. You want to maximize this score.

Output

The first line contains one integer - $L$.

The $(i + 1)^{th}$ line has the following format - $S_i, P_1, P_2, \dots, P_{S_i}$. $P$ is a set of vertices, representing a tree in the remaining forest. The condition $\forall (x,y), (x,y) \in T_{S_i} \iff (P_x, P_y) \in E$ must be satisfied.

We must have that $\sum_{i = 1}^{L} S_i = N$. Every vertex must appear exactly once.

Test Generation

For the first $10$ tests. At first, an array $V$ of length $K$ is generated uniformly under the conditions attached below. Then, we generate a forest containing trees $T_{V_1}, T_{V_2}, \dots, T_{V_K}$ with indices from $1$ to $N$. After this, random edges are added in order to transform the forest into tree $F$. $W$ will be assigned value $\sum_{i = 1}^{K} V_i^3$.

The rest of the tests have random trees. $W$ will be assigned value $21 N$.

Note that the tests are ordered in the same way as presented in the table above.

Test data will be regenerated with different seeds after the contest.