You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个可以看成无向图的城市，上面有 $n$ 个点和 $m$ 条边。

每一天，有若干辆垃圾车按照环形来跑一圈。并且，对于一辆垃圾车， 除了起点以外不能跑两次。

一条路有 $2$ 种状态：清洁的（用 0 表示）或不清洁的（用 1 表示）。每次垃圾车经过，都会改变这条路的状态。

因为有些路上的人不交垃圾清理费，所以市长想要那些路变得不清洁；除此之外的路要清洁。那么，如何安排垃圾车，才能使得市长目的达到呢？

By

感谢 @cn：苏卿念 提供SPJ

输入格式

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

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

你可以认为若存在合法方案，则存在一个卡车经过总边数不超过 $5m$ 的方案。

对于 $60\%$ 分数的数据，有 $m \leqslant 10000$。

输出格式

如果不存在合法方案，输出一行 NIE（波兰语「否」）；

否则按下列格式输出任意一种方案：

• 第一行包含一个整数 $k$，表示卡车行驶环路的总数；
• 接下来 $k$ 行，每行描述一条环路：
  • 首先是一个正整数 $k_i$ 表示环路经过的边数，后接一个空格；
  • 接下来 $k_i + 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

2
3 1 3 2 1
3 4 6 5 4