Snow in Berlandia
Winters in Berlandia are snowy, and this year is no different. Every winter, the government is tasked with clearing the roads of snow, a particularly challenging job in the capital.
The capital of Berlandia can be described as having n intersections and m one-way roads. Each road connects two distinct intersections, x_i and y_i, and is directed from x_i to y_i. The i-th road has w_i tons of snow on it.
To tackle this, the government has hired a private company named "Snow White". Each day, the company dispatches one snowplow truck. The truck begins its route at intersection A, travels through several intersections, and concludes at intersection B. The truck's route can include repeated roads and intersections, including A and B.
Each day, the truck travels from intersection A to intersection B, adhering to traffic rules. Each time the truck passes over a road with snow, it reduces the snow by 1 ton. To avoid accusations of budget waste, the driver is not allowed to drive on roads that are already clear of snow.
Some roads in the city are historically significant due to the presence of government buildings. By the end of the company's work, these historical roads must be completely cleared of snow. The historical center of the capital is at intersection A, ensuring pedestrian access to all historical roads from the center via other historical roads. For pedestrians, roads are considered two-way.
The government pays the company for each day of work, so "Snow White" aims to extend the work over the maximum number of days.
Your task is to determine a sequence of routes from A to B that meets the following criteria: adherence to traffic direction, clearing of historical roads, and maximizing the number of working days.
Input
The first line contains the integers n, m, A, B (2 ≤ n ≤ 100, 0 ≤ m ≤ 5000, 1 ≤ A, B ≤ n, A ≠ B), where n is the number of intersections in the capital, and m is the number of roads. The next m lines each contain four numbers x_i, y_i, w_i, t_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i, 0 ≤ w_i ≤ 100, 0 ≤ t_i ≤ 1), where x_i and y_i are the endpoints of the road, w_i is the snow amount, and t_i indicates the road type (0 for regular, 1 for historical). There can be at most one road between any pair of intersections in each direction.
Output
Output p — the maximum number of working days. The following p lines should describe the daily routes of the snowplow truck. Each route should be a list of intersection numbers, starting with A and ending with B, separated by spaces. If there are multiple solutions, you may output any one; if no solution exists, output 0.