Internet Problem Solving Contest

• Easy input data set – I1
• Hard input data set – I2 (generator)

Cycling is a cheap and healthy way of getting from A to B, plus it is a lot of fun. That is why Peter invited Kamila to join him on an ambitious bike trip around the world. Unfortunately, cycling can sometimes be hard – just imagine having to ascend 1500 meters on some winding road to a mountain pass in the Alps. Different cyclists have a different degree of preference for the ascents. On one side of the spectrum there is Kamila who would like to avoid going uphill completely. On the other side you will find Peter who thinks that flat roads are painfully boring. Now Peter and Kamila have a problem – they need to figure out which route to choose so that they would both enjoy the trip. Help them by finding all the options they have.

Problem specification

There are n towns in the world. The towns are numbered 1 through n. Peter and Kamila want to start the trip in town 1 and end it in town n. Each road is a directed edge from one town to another. Each road has two parameters: the distance d ≥ 0 between its endpoints, and the ascent a ≥ 0. At least one of them is nonzero.

Each cyclist can be described by a single real number p ∈ [0, 1]: their preference for ascents. The value p determines the actual length of each edge for this particular cyclist: an edge with distance d and ascent a will have the length pd + (1 − p)a. For example, Kamila has p = 0 and only cares about ascents. Peter has p = 1: he ignores all ascents and only cares about the total distance.

Different values of p will obviously produce different shortest paths from 1 to n. Your task is to find all values p where the set of shortest paths changes.

Formally, let S(p) be the set of all paths from 1 to n that have the shortest total length for a cyclist with preference p. Find all values p such that 0 < p < 1 and the sets S(p − ε) and S(p + ε) differ for any ε > 0. (The two sets differ if there is some specific path from 1 to n that is among the shortest paths in one setting but not in the other one. Note that p = 0 and p = 1 are by definition never valid answers.)

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing two integers n and m: the number of towns and the number of roads. Next, m lines follow. The i-th of these lines will contain four integers: x_i, y_i, d_i, and a_i (1 ≤ x_i ≤ n; 1 ≤ y_i ≤ n; 0 ≤ d_i; 0 ≤ a_i; 0 < d_i + a_i). These represent a directed road from the town x_i to the town y_i, with distance d_i and ascent a_i. Note that some of the roads may be self-loops (with x_i = y_i) and that each pair of towns can be connected by multiple roads in each direction.

In the easy subproblem I1 you may assume that n ≤ 100, m ≤ 5000, and 0 ≤ d_i, a_i ≤ 10 000.

In the hard subproblem I2 you may assume that n ≤ 5000, m ≤ 500 000, and 0 ≤ d_i, a_i ≤ 500 000.

Because the input file size for subproblem I2 is about 100 MB, you cannot download it directly. Instead, we have provided a small Python 2 program that will generate the file i2.in when executed.

Note that the implementation of this generator might matter.

Output specification

For each test case, find the number v of valid answers and their values p₁ < p₂ < ⋯ < p_v. Output a single line containing the integer v followed by the real numbers p₁ through p_v, in order. Output each p_i to at least 10 decimal places. Any answer that differs from the correct solution by at most 10^− 9 will be accepted.

Note that in some test cases the set of shortest paths never changes. In such case we have v = 0 and thus the output line will contain just a single zero. Notably, this includes all test cases in which it is impossible to get from 1 to n. (In those test cases, each set S(p) is empty.)

Example

Input:

3

2 2
1 2 1 1
1 2 3 0

2 2
1 2 1 0
1 2 1 0

2 0

Output:

1 0.333333333333
0
0

In the first test case there are two roads from 1 to 2. The first road (distance 1, ascent 1) goes across a small hill, the other (distance 3, ascent 0) takes a detour around the hill. The preference between these roads changes at p = 1/3: any cyclist with p > 1/3 will prefer the first road while any cyclist with p < 1/3 will prefer the second one.

In the second test case there are two different roads, but they look the same to any cyclist. Each of them is a shortest path for any value of p.

Finally, in the third case it is impossible to reach the destination.