Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Zer VS EEE

By Zeronfinity · Limits 1s, 512 MB · Custom Checker

Zer is a programmer who has a friend named Nir. Nir always shows off how great EEE is. One day Nir came to Zer with a EEE’ish problem. Nir gave Zer a circuit. The circuit has N nodes and M wires where each wire connects two different nodes. Moreover, a wire that connects node U to node V can only pass electricity from U to V but not vice-versa, that means the wires are uni-directed.

Nir gave Zer a list of these wires detailing which wire connects which nodes. There are also a lower bound and an upper bound for each wire describing the minimum amount of electricity that must pass through the wire and the maximum amount of electricity that can pass through the wire, respectively. Also, according to KCL (Kirchhoff’s Circuit Law), the net amount of electricity entering a node must be equal to the net amount of electricity exiting that node.

Zer has to give a valid configuration for the problem Nir gives. He has to tell the amount of electricity flowing through each wire such that all the above constraints are satisfied. As a good problem solver, your help would be highly appreciated by Zer.

Input

The input starts with two integers N and M, the number of nodes and the number of wires respectively.

Each of the next M lines contains four integers U, V, L, H, stating that a wire connects node U and V such that electricity can pass from U to V and the amount of electricity must be at least L and at most H.

It is guaranteed that no two wires will have exactly the same U and V i.e. there will be at most one wire that allows electricity to pass from a node U to another node V.

Constraints:
1 ≤ N ≤ 100
For each wire,
1 ≤ U, V ≤ N
U != V
0 ≤ L ≤ H ≤ 106

Output

If no valid configuration exists, print NO in a single line.

Otherwise, print YES followed by M lines. Each line should contain the amount of electricity flowing through each wire in the same order as given in input.

If multiple valid configurations exist, print any of them in such a case.

Samples

InputOutput
3 3
1 2 1 2
2 3 0 3
3 1 2 6
YES
2
2
2
InputOutput
3 3
1 2 1 2
2 3 0 3
3 1 4 5
NO
InputOutput
4 5
1 2 1 2
2 3 0 3
3 1 2 6
3 4 1 1
4 3 1 1
YES
2
2
2
1
1


Discussion
Statistics

50% Solution Ratio

mahdi.hasnatEarliest, 1w ago

ShahinFastest, 0.0s

Valentin_ELightest, 655 kB

ShahinShortest, 1289B

Submit

Login to submit