Byteotian Waste Management Company (BWMC) 最近大幅提高了垃圾收集的价格。这导致一些市民停止支付垃圾收集费用，并开始将垃圾倾倒在街道上。结果，Byteburg 的许多街道实际上被垃圾掩埋了。

Byteburg 的街道系统由 $n$ 个交叉路口组成，其中一些交叉路口通过双向街道直接相连。没有两条街道连接同一对交叉路口。有些街道有垃圾，而另一些则没有。

Byteburg 的市长 Byteasar 决定采取前所未有的行动来说服市民支付垃圾收集费用。具体来说，他决定只清理部分街道——即那些大多数居住在街道旁的人支付了垃圾收集费用的街道。另一方面，大多数居住在街道旁的人没有支付垃圾收集费用的街道将保持有垃圾状态——或者如果需要的话——将通过从其他街道收集的垃圾使其变得有垃圾！Byteasar 已经准备好了一张城市地图，上面标明了哪些街道需要清理，哪些街道需要保持或变得有垃圾。不幸的是，BWMC 的员工无法理解他的宏伟计划。然而，他们完全有能力执行简单的指令。

每一条这样的指令包括驾驶垃圾车沿着一条路线行驶，该路线从任意一个交叉路口出发，沿着选择的任何街道行驶，并最终回到出发的同一个交叉路口。然而，在单条路线上，每个交叉路口最多只能访问一次，除了起点和终点——垃圾车显然在那个交叉路口出现了两次。垃圾车在行驶经过有垃圾的街道时会将其清理干净，但另一方面，它会将垃圾倾倒在路线上的干净街道上，使它们变得有垃圾。

Byteasar 想知道是否可以通过发布一系列上述路线指令来实现他的计划。请编写一个程序来确定这样的一组路线，或者得出无法实现的结论，从而帮助他。

输入格式

标准输入的第一行包含两个由单个空格分隔的整数：$n$ 和 $m$ ($1 \le n \le 100\,000$, $1 \le m \le 1\,000\,000$)，分别表示 Byteburg 的交叉路口数量和街道数量。交叉路口编号从 $1$ 到 $n$。接下来的 $m$ 行指定了连续的街道，每行一条。每行包含四个由单个空格分隔的整数：$a, b, s$ 和 $t$ ($1 \le a < b \le n, s, t \in \{0, 1\}$)。这样的四元组表示交叉路口 $a$ 和 $b$ 由一条街道连接，$s$ 表示街道当前是否有垃圾（$0$ 表示干净，$1$ 表示有垃圾），$t$ 表示根据 Byteasar 的计划，街道是否应该有垃圾。

你可以假设，如果存在一组路线可以执行 Byteasar 的计划，那么一定存在一组路线，使得垃圾车行驶的街道总数不超过 $5 \cdot m$。

在占总分 $60\%$ 的测试中，额外满足 $m \le 10\,000$。

输出格式

如果没有一组路线可以让垃圾车执行 Byteasar 的计划，则应在标准输出的第一行（也是唯一一行）打印单词 "NIE"（波兰语中的“不”）。否则，应打印出执行 Byteasar 计划的任意一组路线，且垃圾车行驶的街道总数不超过 $5 \cdot m$。此时，第一行应包含路线集合中的路线数量 $k$。接下来的 $k$ 行应描述这些路线，每行一条。第 $(i+1)$ 行应以一个正整数 $k_i$ 开头，等于第 $i$ 条路线中的街道数量。在单个空格后，应跟随路线中连续的 $k_i+1$ 个交叉路口编号，并以单个空格分隔。

样例

输入 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