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.