30968번 - Blume der Liebe 스페셜 저지

리베 여학원의 정원에는 아름다운 백합이 핀다. 이 백합이 만개한다면 얼마나 좋을까? 시라사기 히메는 슈베스타인 아야노코지 미츠키에게 그저 백합이 활짝 핀 아름다운 광경을 보여주고 싶었다.

리베 여학원에는 여러 개의 쉼터와 산책로로 이루어진 정원이 있다. 한 산책로는 서로 다른 두 쉼터를 양방향으로 잇는다. 서로 다른 두 산책로가 같은 쌍의 쉼터를 연결하는 경우는 없다. 시라사기 히메는 산책로를 산책하면서 백합을 가꾸기로 했다. 하루에 한 번 하는 산책에서는 한 쉼터에서 시작해서 여러 쉼터들을 방문한 후 처음 시작한 쉼터로 돌아온다. 단, 쉼터 사이를 이동할 때는 산책로를 사용해야 하고, 처음 방문한 쉼터로 돌아오기 전에는 같은 쉼터를 두 번 이상 방문할 수 없다. 또한, 한 번 산책을 할 때는 세 곳 이상의 쉼터를 방문해야한다.

히메는 여러 날 동안 산책을 하며, 산책로를 방문할 때마다 산책로에 있는 백합에 물을 준다. 물을 너무 많이 주면 뿌리가 썩어버릴 것이고 너무 적게 주면 잎이 마를 것이기에, 히메는 모든 산책로에 있는 백합에게 정확히 $4$번씩 물을 주려고 한다. 히메가 모든 산책로에 적절히 물을 줄 수 있도록 히메의 산책 계획을 정해주자.

첫 번째 줄에는 리베 여학원의 정원의 쉼터의 수 $N$과 산책로의 수 $M$이 공백으로 구분되어 주어진다. $(3 \le N \le 200;$ $3 \le M \le 300)$

다음 $M$개의 줄의 각 줄에는 산책로가 잇는 두 정원의 번호 $u, v$가 공백으로 구분되어 주어진다. $(1 \le u < v \le N)$ 같은 $(u, v)$쌍이 여럿 주어지는 경우는 없다.

히메가 모든 산책로를 정확히 $4$번씩 방문하는 방법이 존재하지 않으면 첫 줄에 $-1$을 출력한다.

히메가 모든 산책로를 정확히 $4$번씩 방문하는 방법이 존재하는 경우, 첫 줄에 산책을 진행하는 날 수 $K$를 출력한다. $\left(4 \le K \le \frac{4M}{3}\right)$

다음 $K$줄의 각 줄에는 산책 일정을 $l$ $p_1$ $p_2$ $\cdots$ $p_l$과 같은 방법으로 공백으로 구분하여 출력한다. $(3 \le l \le N)$ 이는 $p_1, p_2, \cdots, p_l$번 쉼터를 차례로 방문하고, 다시 $p_1$번 쉼터로 돌아오는 산책 일정을 의미한다. $p_i$와 $p_{i+1}$번 쉼터 사이에 그리고 $p_l$과 $p_1$번 쉼터 사이에는 산책로가 존재해야하며 $(1 \le i \lt l)$, 모든 $p_j$는 서로 달라야 한다. $(1 \le j \le l)$

$K$개의 산책 일정을 모두 한 번씩 거친 이후, 모든 산책로는 $4$번씩 방문되어야한다.