E. Educational Problem
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a directed graph with $$$N$$$ vertices and $$$M$$$ edges, compute the maximum flow from the source vertex $$$1$$$ to the sink vertex $$$N$$$.

You are not a baby, you know what maximum flow is.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ — the number of vertices and edges, respectively.

Each of the next $$$M$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$c_i$$$, describing a directed edge from vertex $$$u_i$$$ to vertex $$$v_i$$$ with capacity $$$c_i$$$.

  • $$$2 \leq N \leq 200$$$
  • $$$0 \leq M \leq N \cdot (N - 1)$$$
  • $$$1 \leq u_i, v_i\leq N$$$
  • $$$1 \leq c_i \leq 10^9$$$
  • The graph contains no self-loops and no multiple edges.
Output

Print an integer on the first line — the maximum flow value from vertex $$$1$$$ to vertex $$$N$$$.

On the second line, print an integer $$$p$$$ — the number of flow paths used in your decomposition.

Then, print $$$p$$$ lines, each describing one flow path in the following format:

  • Suppose the $$$i$$$-th path sends $$$x_i$$$ units of flow from vertex $$$1$$$ to vertex $$$N$$$, following the path $$$1 = v_1, v_2, \ldots, v_{k_i} = N$$$ (the path can be non-simple).
  • Output $$$k_i + 2$$$ integers: first, the number $$$x_i$$$ (the amount of flow sent along the path), followed by $$$k_i$$$ (the length of the path), and then the $$$k_i$$$ vertices $$$v_1, v_2, \ldots, v_{k_i}$$$.

Multiple valid outputs may exist. Your output will be considered correct if it satisfies all of the following conditions:

  • $$$0 \leq p \leq 5 \cdot 10^4$$$.
  • $$$\sum_{i=1}^{p} x_i$$$ equals the maximum flow value.
  • For each edge $$$(u_i, v_i)$$$ with capacity $$$c_i$$$, the total flow across all paths using this edge does not exceed $$$c_i$$$.
  • Every path must use only edges present in the input, and must start at vertex $$$1$$$ and end at vertex $$$N$$$.
Examples
Input
4 5
1 2 4
2 3 2
3 4 3
1 3 1
2 4 1
Output
4
3
1 3 1 2 4
1 3 1 3 4
2 4 1 2 3 4
Input
4 2
1 2 10
3 4 10
Output
0
0