Problem : 99 - 垃圾處理

Special Judge

Problem Statistics

Solved Member: 17　　Submission: 118　　User Tried: 18

Statement:

兔子國是由 N 個由1編號到N的星球以及 M 條不同的道路所連接而成的。其中，任意兩個星球最多只會有一條道路連接。
兔子國的垃圾處理方法，基本上跟地球是差不多的。有很多台垃圾車，每台垃圾車從一個星球出發，經過某一些道路，沿途收集道路上的垃圾；最後回到原本的星球。

由於石油漲價的關係，兔王也決定調漲清潔費的部份。非常不妙的，這項舉動引起了人民們的不滿，許多人民開始決定拒繳清潔費。
兔王不干心，因此他決定做一個瘋狂的舉動－　讓某些繳清潔費比例較低的道路變成垃圾掩埋場！

詳細情況是這樣的，兔王已經整理出了每條道路的最初狀態(乾淨或髒)，以及最終狀態(乾淨或髒)。

每台垃圾車依據以下的規則在行駛：
1.從任意一個點出發，經過若干條道路回到原點。
2.每經過一條路，若它是髒的，則會做清潔的工作(變乾淨)；反之若它是乾淨的，則經過就會順便把垃圾倒在那裡(變髒)。
3.除了起點跟終點是一樣的以外，沒有點會被同一台垃圾車重複經過兩次。

兔子王想知道，他是否有辦法透過有限台的垃圾車達到他邪惡的目的。
並且，為了控制成本，他希望所有垃圾車所經過的路徑長總和在 5*M 以內。

Input:Output:

輸入最開始有兩個正整數 N,M(N ≤ 100000; M ≤ 1000000)，代表星球數以及道路數。
接下來 M 行每行會有 4 個整數 A,B,S,T，代表 A 與 B 之間存在一條雙向的道路，起始狀態為 S ，最終狀態希望為 T。
其中S和T為0或1之一的整數，0代表乾淨的狀態，1代表髒的狀態。

在 60% 的測資當中滿足 M ≤ 10000。

請輸出隨便一種滿足要求的答案。

若沒有辦法達成兔王的計畫，請輸出 "NIE" 。
否則，第 1 行請輸出一個正整數 k ，代表需要幾台垃圾車。

接下來的 k 行，每行為對一台垃圾車所要走的路的描述。
每行第一個數字 Ni 代表第 i 台垃圾車所要走的路徑長，後面 Ni+1(起點與終點重複，故長度Ni的路徑需要輸出Ni+1個點) 個數字依序為垃圾車所要經過的點。

Sample Input:Sample Output:

SAMPLE A:
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

SAMPLE B:
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

SAMPLE A:
2
3 1 3 2 1
3 4 6 5 4

SAMPLE B:
NIE

HINT:

以上為兩個範例測資的圖。
細線/粗線代表起始狀態的乾淨/髒。
虛線/實線代表最終狀態的乾淨/髒。

Source:

POI 18 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
1-ocen	1000ms	262144kb
1	1000ms	262144kb	10
2-ocen	1000ms	262144kb
2	1000ms	262144kb	10
3-ocen	1000ms	262144kb
3-1	1000ms	262144kb	10
3-2	1000ms	262144kb
4-ocen	1000ms	262144kb
4-1	1000ms	262144kb	10
4-2	1000ms	262144kb
5-ocen	7500ms	262144kb
5-1	1000ms	262144kb	10
5-2	1000ms	262144kb
6-1	1000ms	262144kb	10
6-2	1000ms	262144kb
7-1	18000ms	262144kb	10
7-2	18000ms	262144kb
8-1	18000ms	262144kb	10
8-2	18000ms	262144kb
9-1	18000ms	262144kb	10
9-2	18000ms	262144kb
10-1	18000ms	262144kb	10
10-2	18000ms	262144kb