Description

There is a city that can be regarded as an undirected graph with $n$ vertices and $m$ edges.

Every day, several garbage trucks each travel one loop along a cycle. Moreover, for any one garbage truck, it cannot visit any vertex twice except returning to its starting vertex at the end.

Each road has 2 states: clean (denoted by 0) or dirty (denoted by 1). Every time a garbage truck passes an edge, the state of that edge toggles.

Because some people on certain roads do not pay the garbage collection fee, the mayor wants those roads to become dirty; all other roads should be clean. How should we schedule the garbage trucks to achieve the mayor’s goal?

By

Thanks to @cn: 苏卿念 for providing the SPJ.

Description

Input Format

The first line contains two positive integers $n$ and $m$ $（ 1 \leqslant n \leqslant 100000，1 \leqslant m \leqslant 1000000）$, the number of vertices and edges of the graph.

The next $m$ lines each contain four space-separated integers $a, b, s, t$ （ $1 \leqslant a \leqslant b \leqslant n$ , $s，t \in \lbrace0,1\rbrace$ ）, describing an edge connecting vertices $a$ and $b$, whose initial state and target state are $s$ and $t$, respectively.

You may assume that if a valid plan exists, then there is a plan in which the total number of edges traversed by all trucks does not exceed $5m$.

For $60\%$ of the testdata, $m \leqslant 10000$.

Output Format

If no valid plan exists, output a single line NIE (Polish for "no").

Otherwise, output any valid plan in the following format:

• The first line contains an integer $k$, the total number of cycles (routes) traveled by the trucks.
• Then output $k$ lines, each describing one cycle:
  • First, a positive integer $k_i$ indicating the number of edges on the cycle, followed by a space;
  • Then $k_i + 1$ integers separated by spaces, giving the vertex indices along the cycle in order.

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

Hint

Translated by ChatGPT 5