407691: GYM102875 E Eliminate the Virus

Servers in the Biscotti kingdom network has been attacked by a computer virus! Yukikaze, the Administrator, is trying to eliminate the virus using a specialized anti-virus program.

The network of the Biscotti kingdom is formed by some nodes and some bidirectional links between the nodes. Yukikaze knows that at the end of each second, the virus will transmit its clone from a node to the neighbors of the node, then destroy itself in the origin node. The neighbors of a node are nodes directly connected to it.

Yukikaze needs to design a strategy for the program, then the program will follow the strategy to find and destroy the virus. A strategy consists of a sequence of (a finite number of) steps. In each step, the anti-virus program will clean up several nodes in the network. At the beginning of each second, a step will be executed by the program. Steps are executed sequentially (step by step, from the first step to the last step). When every step in the designated strategy is executed at least once, the program halts. If the virus doesn't exist in the network anymore after the program halts, then the strategy is considered valid.

Unfortunately, the ability of the anti-virus program is limited by a parameter $$$k$$$, denoting the maximum number of nodes the program can affect in each step. Before the anti-virus program launches, every node in the network was infected by the virus. Design a strategy to eliminate the virus from every node in the network or declare it's impossible.

The first line contains three integers $$$n\ (2 \leq n \leq 16)$$$, $$$m\ (1 \leq m \leq \frac 12 n(n-1))$$$, $$$k\ (1 \leq k \leq n)$$$, denoting the number of nodes in the network, the number of distinct links in the network and the parameter of anti-virus program.

For the next $$$m$$$ lines, each line contains two integers $$$u,v\ (1 \leq u, v \leq n, u \neq v)$$$, denoting an bidirectional link between node $$$u$$$ and $$$v$$$.

It's guaranteed that there will be no isolated node in the network (i.e., a node which is not connected to any other node) and no pair of nodes is connected by more than one link.

If the virus won't be eliminated from the network in any possible strategy, output $$$-1$$$ in a single line.

Otherwise, output the strategy in the following format.

The first line of the output should contain a single integer $$$L\ (1 \leq L \leq 100)$$$, denoting the number of steps.

Each of the following $$$L$$$ lines should contain a non-empty string consisting of lowercase letters which length is less or equal to $$$k$$$, denoting the nodes to clean up in each step. If the $$$i$$$-th lower case letter is presented in the $$$(j+1)$$$-th line of the output, then the $$$i$$$-th node will be cleaned up in the $$$j$$$-th step.

It's guaranteed that for every input test case if there exists a valid strategy, then there exists a valid strategy using less than or equal to $$$100$$$ steps.

Any valid strategy satisfying the constraint $$$1 \leq L \leq 100$$$ is acceptable.

5 4 2
1 2
2 3
3 4
2 5

2
bd
bd

2 1 1
1 2

2
b
b

5 5 2
1 2
2 3
3 4
4 5
5 1

4
ce
be
de
ac

Try to consider the strategy on a $$$4 \times 3$$$ grid graph.