Description

果果有一张 $n$ 个点 $m$ 条边的无向图，每条边均为黑白二色之一，且有一个黑或白的目标颜色，如果果果把边上的颜色都变为了目标颜色，那么他就切掉了这道题。

果果有一种切题技巧，她每次可以选择一个多边形（不经过重复边或起点以外结点的环）回到出发点，将所有经过边的颜色反转，即黑色变为白色，白色变为黑色。他可以使用这样的技巧很多次。

你需要帮助果果给出一个切题方案，使得每条边最终都变为目标颜色。

当然果果的切题技巧可能不够优秀，在无论如何都切不掉这道题的情况下，你需要输出 -1。

Input Format

输入的第一行包含两个空格分隔的正整数 $n$ 和 $m$（$1 \leq n \leq 100\,000$，$1 \leq m \leq 1\,000\,000$），表示图的点数和边数。

接下来 $m$ 行，每行包含四个空格分隔的正整数 $a, b, s, t$（$1 \leq a \lt b \leq n$，$s, t \in \{0, 1\}$），表示一条联结结点 $a$ 与 $b$ 的边，初始颜色和目标颜色分别为 $s$ 与 $t$。

果果相信对于一道他可以切掉的题，只需要总边数不超过 $5m$ 的多边形即可。

Output Format

如果果果切不掉这道题，输出 -1；
否则按下列格式输出任意一种方案：

• 第一行包含一个整数 $k$，表示切题技巧使用的总次数；
• 接下来 $k$ 行，每行描述一个多边形：
  • 首先是一个正整数 $k_i$ 表示多边形的边数，后接一个空格；
  • 接下来 $k_i + 1$ 个空格分隔的整数，依次表示多边形顶点的编号。

你需要保证你的多边形总边数不超过 $5m$。

Sample

样例输入 1

6 8
1 2 0 1
2 3 1 0
1 3 0 1
2 4 0 0
3 5 1 1
4 5 0 1
5 6 0 1
4 6 0 1

样例输出 1

2
3 1 3 2 1
3 4 6 5 4

样例输入 2

6 8
1 2 0 1
2 3 1 0
1 3 0 1
2 4 0 0
3 5 1 1
4 5 0 1
5 6 0 1
4 6 0 0

样例输出 2

-1

Hint

** Subtask #1 (6 points): $n \leq 20, m \leq 30$**
** Subtask #2 (8 points): $n \leq 500, m \leq 5 \times 10^3$**
** Subtask #3 (12 points): $n \leq 2000, m \leq 5 \times 10^3$**
** Subtask #4 (14 points): $n \leq 5000, m \leq 10^4$**
** Subtask #5 (23 points): $n \leq 10^4, m \leq 5 \times 10^5$**
** Subtask #6 (37 points): $n \leq 10^5, m \leq 10^6$**
** 对于所有数据，保证这是一张无重边的图。**
** 友情提示：请注意输入输出效率。 **