Save the Earth!

A squad of superheroes is rushing to help the defenders of Earth in the battle against Thanos. The superheroes are currently on Titan, and they have only one space shuttle. The shuttle holds $k$ passengers and one pilot. The squad consists of one wise leader and $n$ other superheroes. Some pairs of superheroes dislike each other, may quarrel, or even harm one another. However, when the leader is nearby, superheroes never conflict, because the leader strictly stops it.

The leader will pilot the shuttle. The leader wants to know whether all superheroes can be transported to Earth. The transport works as follows:

• At most $k$ superheroes board the shuttle together with the leader. Among the superheroes left on Titan, there must be no conflicting pair, or disastrous consequences may follow.
• The shuttle flies to Earth. During the flight, the superheroes on board are next to the leader, so they do not fight.
• On Earth, all superheroes on the shuttle get off. Among the superheroes now on Earth, a conflicting pair may exist. They do not fight, because the leader is nearby.
• At most $k$ superheroes board the shuttle. Among the superheroes left on Earth, there must be no conflicting pair.
• The shuttle flies to Titan.
• On Titan, all superheroes on the shuttle get off. Among the superheroes on Titan at that moment, a conflicting pair may exist.

These steps repeat in a cycle until all superheroes and the leader are on Earth. The leader may fly between planets without any superheroes if needed. If a planet has no leader, it must have no conflicting pair. There are no other restrictions on conflicting pairs.

You are given the list of conflicting pairs. Help the leader find a sequence of actions that transports all superheroes to Earth, or report that it is impossible. Minimizing the number of flights is not required. However, the leader wants a plan with at most $100\,000$ flights. It can be proven under these constraints that if a way to deliver everyone to Earth exists, a way with at most $100\,000$ flights also exists.

The first line contains three integers $n$, $m$, and $k$: the number of superheroes, the number of conflicting pairs, and the number of superheroes that fit into the shuttle ($1 \le n \le 15$, $0 \le m \le n \cdot (n - 1) / 2$, $1 \le k \le 15$).

Each of the next $m$ lines contains a pair of integers $a_i$, $b_i$, the numbers of superheroes that conflict ($1 \le a_i, b_i \le n$, $a_i \neq b_i$).

Each pair of superheroes appears at most once. If the input contains the pair $a_i$, $b_i$, then the pair $b_i$, $a_i$ does not appear.

If it is impossible to transport all superheroes and the leader to Earth, print $-1$ on a single line.

Otherwise, print on the first line the integer $t$, the number of flights the shuttle makes so that all superheroes and the leader end up on Earth ($t \le 100\,000$). On each of the next $t$ lines, print the list of superheroes on the shuttle during the $i$-th flight. Begin the line with $q_i$, the size of the list, followed by $q_i$ distinct numbers, the numbers of the superheroes on the shuttle during that flight.