Fox, Chicken, and Corn
当前没有测试数据。
Description
After learning $10^{100}$ data structures, Nea1 has decided to return to China and become a farmer!
Nea1 has $n$ chickens, labeled from $1$ to $n$. The relationships among the chickens can be described by a forest with $n - 2$ edges, where edges represent incompatibility. In other words:
- There are $n - 2$ pairs of chickens that are incompatible.
- There do not exist distinct integers $c_1, c_2, ..., c_k$ such that $k \geq 3$, chickens $c_1$ and $c_k$ are incompatible, and chickens $c_i$ and $c_{i + 1}$ are incompatible for all $1 \leq i < k$.
- A chicken is never incompatible with itself, and all pairs are distinct.
Additionally, every chicken is incompatible with at least one other chicken.
Nea1 would like to cross a river using a rowboat that can hold at most $k$ chickens (along with himself) at once. Is it possible for him to bring all $n$ chickens across the river such that no two incompatible chickens are ever left unattended?
More formally, let $A$ and $B$ represent the sets of chickens on both sides of the river. Initially, $A = \{1, 2, ..., n\}$ and $B$ is the empty set. Nea1 can perform a sequence of operations. On the $i$th operation, he does the following:
- If $i$ is odd, he picks some subset $M \subseteq A$ such that $|M| \leq k$, and there do not exist $i, j \in A - M$ such that chickens $i$ and $j$ are incompatible. Afterwards, he sets $A$ to $A - M$ and sets $B$ to $B \cup M$. Note that afterwards, $B$ is allowed to contain integers representing incompatible chickens.
- If $i$ is even, he picks some subset $M \subseteq B$ such that $|M| \leq k$, and there do not exist $i, j \in B - M$ such that chickens $i$ and $j$ are incompatible. Afterwards, he sets $B$ to $B - M$ and sets $A$ to $A \cup M$. Note that afterwards, $A$ is allowed to contain integers representing incompatible chickens.
Does there exist any sequence of operations such that at the end, $A$ is the empty set and $B = \{1, 2, ..., n\}$? If so, output any sequence that accomplishes this.
The first line of input consists of two space-separated integers $n$ and $k$ $(4 \leq n \leq 1500, 1 \leq k \leq n)$.
The following $n - 2$ lines each consist of two space-separated integers $u$ and $v$ $(1 \leq u, v \leq n, u \neq v)$, representing incompatibility between chickens $u$ and $v$. It is guaranteed that the incompatibility graph is a forest, and that every chicken is incompatible with at least one other chicken.
If there exists some sequence of operations that results in all chickens crossing the river, output any such sequence as follows:
On the first line, output a single integer $o$ $(1 \leq o \leq 4000)$, representing the number of operations.
On each of the following $m$ lines, output a space-separated integer sequence $s, m_1, m_2, ..., m_s$ $(0 \leq s \leq k, 1 \leq m_i \leq n)$. On the $i$th line, $s$ should describe the size of the chosen subset $M$ used in the $i$th operation. All $m_i$ should be distinct and members of $M$.
Otherwise, if it is impossible for the chickens to cross the river, output a single line with the string NO.
It can be proven that if there exists any working sequence of operations, there also exists one with at most $4000$ operations under the constraints of the problem.
Input
The first line of input consists of two space-separated integers $n$ and $k$ $(4 \leq n \leq 1500, 1 \leq k \leq n)$.
The following $n - 2$ lines each consist of two space-separated integers $u$ and $v$ $(1 \leq u, v \leq n, u \neq v)$, representing incompatibility between chickens $u$ and $v$. It is guaranteed that the incompatibility graph is a forest, and that every chicken is incompatible with at least one other chicken.
Output
If there exists some sequence of operations that results in all chickens crossing the river, output any such sequence as follows:
On the first line, output a single integer $o$ $(1 \leq o \leq 4000)$, representing the number of operations.
On each of the following $m$ lines, output a space-separated integer sequence $s, m_1, m_2, ..., m_s$ $(0 \leq s \leq k, 1 \leq m_i \leq n)$. On the $i$th line, $s$ should describe the size of the chosen subset $M$ used in the $i$th operation. All $m_i$ should be distinct and members of $M$.
Otherwise, if it is impossible for the chickens to cross the river, output a single line with the string NO.
It can be proven that if there exists any working sequence of operations, there also exists one with at most $4000$ operations under the constraints of the problem.
6 4
1 2
2 3
2 4
5 6
4 4
1 2
3 4
4 1
1 2
3 4
3
4 1 2 3 5
1 2
3 6 2 4
1
4 1 2 3 4
NO
Note
In the first sample test case, the incompatibility graph looks as follows:
Here are 3 operations in one of the possible solutions:
In the second sample, all chickens can be moved to the other side in a single operation.
In the third sample, it can be proven that no solution exists.