Snow in Berlandia#4592
Winters in Berlandia are snowy, and this year is no exception. Every winter, the government faces the task of clearing the roads of snow, which is especially challenging in the capital.
The capital of Berlandia can be represented as having intersections and one-way roads. Each road connects two distinct intersections x_i and y_i and is directed from x_i to y_i. The -th road has w_i tons of snow on it.
To accomplish this, the government has hired a private company named "Snow White." Each day, the company sends out a snowplow. It starts its route at intersection , passes through several intersections, and ends at intersection . The route may include repeated roads and intersections, including and .
Each day, the snowplow travels from to , always following the traffic rules. Every pass over a snowy road reduces the amount of snow on that road by ton. Since residents might accuse the government of wasting the budget, the driver is forbidden from taking the snowplow onto a road that has already been cleared of snow.
Some of the city's roads are historically significant because government buildings are located on them. Therefore, by the time "Snow White" finishes its work, all historical roads must be free of snow. It is known that intersection is the historical center of the capital, meaning that all historical roads are accessible by foot from the center via other historical roads. Remember that, for pedestrians, roads are considered bidirectional.
The government pays the company for each day worked, so the management of "Snow White" seeks to maximize the number of working days.
Your task is to determine a sequence of routes from to that satisfies the following conditions: obeying road directions, clearing all historical roads, and maximizing the number of working days.
The first line contains integers , , , (2 \le n \le 100, 0 \le m \le 5000, 1 \le A, B \le n, A \ne B), where — the number of intersections in the capital of Berlandia, — the number of roads. The next lines each contain four integers x_i, y_i, w_i, t_i (1 \le x_i, y_i \le n, x_i \ne y_i, 0 \le w_i \le 100, 0 \le t_i \le 1), where x_i, y_i — the endpoints of the road, w_i — the amount of snow on it, t_i — the road type ( means an ordinary road, means historical). There may be at most one road between any pair of intersections in each direction.
Output — the maximum possible number of working days. The next lines should describe the daily routes of the snowplow. Each route should be a list of intersections, starting with and ending with , separated by spaces. If there are multiple solutions, you may output any of them. If there is no solution, output .
Example 1