Power Crisis

Jakarta is the largest city in Indonesia which deals with a large power consumption. It often suffers from blackout as PLN (the state electricity company) has difficulty in maintaining a stable electricity power for the city. It was so bad such that a breakdown in one of PLN's electric substation is enough to force a single area to lit up candles for one long night. In order to overcome this problem, PLN comes up with a plan to build yet the largest power plant in Indonesia. The power plant will be located at the east coast of Java and provide sufficient electricity power to Jakarta through series of cables.

There are N stations numbered from 1 to N. Station 1 is set as the power plant and station N as Jakarta. These stations are connected with cables that transmit electricity power from one station to another. Each cable transmits power in one specific direction (e.g. electricity power only travels in cable C from station A to station B and not the other way around). As each cable is made of an expensive special material, it consists of two important properties that have to be considered: a capacity of C_i and a minimum required power of L_i. These two properties define that a cable i has to transmit at least L_i power and is not able to transmit more than C_i power. A failure in transmitting power less than L_i will result in a fast deterioration of cable i.

While the power plant is able to generate any amount of electricity power and Jakarta is able to receive any amount of electricity power happily, PLN requires an equilibrium constraint to be applied to all stations (excepts for the power plant and Jakarta). Equilibrium constraint defines that the total amount of incoming power should be equal to the total amount of outgoing power from the station. So take note that there are 2 types of constraints that they have to maintain:

1. equilibrium constraint for all stations (excepts for the power plant and Jakarta)
2. the electricity power which is transmitted on each cable is between L_i and C_i, inclusive.

The blueprint of the plan is prepared and money is not a problem. However, they are still not sure whether the plan is feasible. They wonder whether it is possible to transmit all these power from the power plant to Jakarta such that all cables satisfy their L_i power requirement while maintaining the equilibrium constraint for all stations (except for the power plant and Jakarta). Can you help them?

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with two integers N and M (2 ≤ N ≤ 50) denoting the number of stations and cables respectively. All stations are numbered from 1 to N with station 1 as power plant and station N as Jakarta. The following M lines each contains four integers A_i, B_i, L_i and C_i (1 ≤ A_i, B_i ≤ N; A_i ≠ N; B_i ≠ 1; A_i ≠ B_i; 0 ≤ L_i ≤ C_i ≤ 100) representing a cable which able to transmit electricity power from station A_i to station B_i with minimum required power L_i and the maximum capacity C_i. You may assume that there is at most one cable which able to transmit electricity power from station A_i to station B_i for all pair of A_i and B_i.

Output

For each case, output in a line "Case #X: Y" where X is the case number starts from 1 and Y is either " YES" or " NO" (without quotes) denoting whether the plan is feasible or not.

5
3 2
1 2 1 5
2 3 4 10
3 2
1 2 1 3
2 3 4 10
4 5
1 2 1 8
1 3 2 5
2 3 5 6
2 4 2 10
3 4 4 10
4 5
1 2 2 10
1 3 2 4
2 3 3 7
2 4 7 15
3 4 8 10
5 5
1 2 0 1
2 3 2 10
3 4 0 10
4 2 0 10
3 5 0 1

Case #1: YES
Case #2: NO
Case #3: YES
Case #4: NO
Case #5: YES

Explanation for the 1^st sample input.

S1 (station 1) can transmit either 4 or 5 electricity power to S2, and S2 further transfer it to S3.

Explanation for the 2^nd sample input.

S1 can transmit at most 3 electricity power to S2. However, S2 needs to transfer at least 4 power to S3. Therefore, this plan is not feasible.

Explanation for the 3^rd sample input.

Here is a possible electricity power transmission:

• S1 to S2: 7
• S1 to S3: 2
• S2 to S3: 5
• S2 to S4: 2
• S3 to S4: 7

Explanation for the 4^th sample input.

S1 can transmit at most 10 electricity power to S2 and S2 will divide the electricity power to S3 (3 electricity power) and S4 (7 electricity power) to fulfill the minimum power requirement. Meanwhile S1 can transmit at most 4 electricity power to S3 and remember that S3 already received 3 electricity power from S2. However, S3 needs to transmit a minimal of 8 electricity power to S4, but it has only a total of 7 incoming electricity power (4 from S1 and 3 from S2). Thus, the plan is not feasible.

Explanation for the 5^th sample input.

There are 5 stations, 5 cables and each cable has minimum required power and maximum capacity L_i..C_i (e.g., 2..10 means L_i=2 and C_i=10) as shown in Figure 1. The red arrow (2-3-4-2) corresponds to the transmitted electricity power of 2. As you might have noticed, these power do not come from the power plant (station 1); however, the equilibrium constraint is maintained and all cables satisfy their minimum required power and maximum capacity. Therefore, the power transmission in Figure 1 is a valid one.

Figure 1