Circulation#5446
Let us define a circulation as a flow with total value . You are given a directed graph, where each edge has a specified lower and upper capacity. For each directed edge from vertex to vertex , let f_{ij} denote the flow, l_{ij} the lower bound, and c_{ij} the upper bound. The flow must satisfy l_{ij} \leq f_{ij} \leq c_{ij} for every edge.
Your task is to determine whether there exists a circulation that meets all these constraints.
The first line contains two integers and (1 \leq N \leq 200, 0 \leq M \leq 15000) — the number of vertices and edges, respectively. The next lines describe the edges. Each line contains four integers , , l_{ij}, c_{ij} (1 \leq i, j \leq N, 0 \leq l_{ij} \leq c_{ij} \leq 10^5), indicating an edge from vertex to vertex with lower bound l_{ij} and upper bound c_{ij}. It is guaranteed that if an edge from to exists, then there is no edge from to .
If it is impossible to find a valid circulation, output NO. Otherwise, print YES on the first line. Then, for each of the edges (in input order), print the value of the flow along that edge. For each edge from to , the flow f_{ij} must satisfy l_{ij} \leq f_{ij} \leq c_{ij}.
Example 1