#2162. 「POI2011 R2 Day1」Garbage

内存限制:256 MiB 时间限制:600 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: ceba_robot

题目描述

译自 POI 2011 Round 2. Day 1. B「Garbage

给定一张 nnn 个点 mmm 条边的无向图,每条边居黑白二色之一,且有一个黑或白的目标颜色。

有一辆卡车,可以从任意一个结点开始,经过一个简单环(不经过重复边或起点以外结点的环)回到出发点,将所有经过边的颜色反转,即黑色变为白色,白色变为黑色。卡车可以从不同的结点出发行走若干次。

请给出一个合法的方案,使得每条边最终都变为目标颜色,或判定不可行。


The Byteotian Waste Management Company (BWMC) has drastically raised the price of garbage collection lately. This caused some of the citizens to stop paying for collecting their garbage and start disposing of it in the streets. Consequently, many streets of Byteburg are literally buried under litter.

The street system of Byteburg consists of n n n intersections, some of which are directly connected with bidirectional streets. No two streets connect the same pair of intersections. Some of the streets are littered while others are not.

The mayor of Byteburg, Byteasar, has decided on an unprecedented action to persuade the citizens to pay for waste collection. Namely, he decided to clean only some of the streets - precisely those that the majority of people living on paid for garbage collection. The streets that the majority of people living on did not pay for waste collection, on the other hand, will thus remain littered - or if it is called for - will become littered by the garbage collected from other streets! Byteasar has already prepared a city map with the streets to be cleaned and to remain or become littered marked on. Unfortunately, the BWMC employees cannot comprehend his master plan. They are, however, quite capable of carrying out simple instructions.

A single such instruction consists in driving the garbage truck along a route that starts on an arbitrary intersection, goes along any streets of choice, and ending on the very same intersection that it started on. However, every intersection can be visited at most once on a single route, except for the one it starts and ends with-the garbage truck obviously appears twice on that one. The truck cleans a littered street it rides along, but on the other hand it dumps the waste on the clean streets along its route, making them littered.

Byteasar wonders if it is possible to execute his plan by issuing a number of aforementioned route instructions. Help him out by writing a program that determines a set of such routes or concludes that it is impossible.

输入格式

输入的第一行包含两个空格分隔的正整数 nnnmmm1≤n≤100 0001 \leq n \leq 100\,0001n1000001≤m≤1 000 0001 \leq m \leq 1\,000\,0001m1000000),表示图的点数和边数。

接下来 mmm 行,每行包含四个空格分隔的正整数 a,b,s,ta, b, s, ta,b,s,t1≤a<b≤n1 \leq a \lt b \leq n1a<bns,t∈{0,1}s, t \in \{0, 1\}s,t{0,1}),表示一条联结结点 aaabbb 的边,初始颜色和目标颜色分别为 sssttt

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

对于 60%60\%60% 分数的数据,有 m≤10 000m \leq 10\,000m10000


There are two integers, separated by a single space, in the first line of the standard input: n n n and m m m(1≤n≤100000 1 \le n \le 100000 1n100000, 1≤m≤1000000 1 \le m \le 1000000 1m1000000), denoting the number of intersections and the number of streets in Byteburg, respectively. The intersections are numbered from 1 1 1 to n n n. The following m m m lines specify successive streets, one per line. Each of those lines holds four integers separated by single spaces: a a a, b b b, s s s and t t t(1≤a<b≤n 1 \le a \lt b \le n 1a<bn, s,t∈{0,1} s, t \in \{0, 1\} s,t{0,1}). Such a quadruple specifies that the intersections a a a and b b b are connected with a street, s s s tells if the street is currently littered (0 0 0 means clean, while 1 1 1 means littered), and t t t tells if the street should be littered according to Byteasar's plan.

You may assume that if there exists a set of routes to carry out Byteasar's plan, then there is one in which the total number of streets that the garbage truck follows does not exceed 5⋅m 5 \cdot m 5m.

In tests worth 60% of the points it additionally holds that m≤10000 m \le 10000 m10000.

输出格式

如果不存在合法方案,输出一行 NIE(波兰语「否」);

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

  • 第一行包含一个整数 kkk,表示卡车行驶环路的总数;
  • 接下来 kkk 行,每行描述一条环路:
    • 首先是一个正整数 kik_iki 表示环路经过的边数,后接一个空格;
    • 接下来 ki+1k_i + 1ki+1 个空格分隔的整数,依次表示环路上结点的编号。

If there is no set of routes for the garbage truck to execute Byteasar's plan, then the word "NIE" (no in Polish) should be printed out to the first and only line of the standard output. Otherwise, an arbitrary set of routes that does execute Byteasar's plan and has the truck move along no more than 5⋅m 5 \cdot m 5m streets in total should be printed out. Then the first line should hold the number k k k of routes in the set. The following k k k lines should describe the routes, one per line. The (i+1) (i + 1) (i+1)-th line should start with a positive integer ki k_i ki equal to the number of streets in the i i i-th route. After a single space, ki+1 k_i +1 ki+1 numbers of successive intersections along the route should follow, separated by single spaces.

样例

细线=初始白色,粗线=初始黑色;
虚线=目标白色,实线=目标黑色。

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

smizad1.gif

样例输出 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

smizad2.gif

样例输出 2

NIE

The clean streets are drawn with a thin line in the figure, whereas the littered streets are drawn with a thick line. The streets that are to be clean are drawn with a dashed line, while those that are to be littered are drawn with a solid line.

For the input data

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

smizad1.gif

one of correct results is:

2
3 1 3 2 1
3 4 6 5 4

whereas for the following input data:

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

smizad2.gif

the correct result is:

NIE

数据范围与提示

Task author: Michal Pilipczuk.
SPJ: ceba.
Translation: Red Scarf.