#P2188. 无源汇上下界可行流

无源汇上下界可行流

无源汇上下界可行流

题目描述

给定一个包含 nn 个点 mm 条边的有向图,每条边都有一个流量下界和流量上界。

求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。

本题不唯一的可行方案输出任意一种即可(使用 Special Judge)。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 mm 行,每行包含四个整数 a,b,c,da,b,c,d,表示点 aa 和 bb 之间存在一条有向边,该边的流量下界为 cc,流量上界为 dd。

点编号从 11 到 nn。

输出格式

如果存在可行方案,则第一行输出 YES,接下来 mm 行,每行输出一个整数,其中第 ii 行的整数表示输入的第 ii 条边的流量。

如果不存在可行方案,直接输出一行 NO。

如果可行方案不唯一,则输出任意一种方案即可。

样例

输入样例 1

4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

输出样例 1

YES
1
2
3
2
1
1

(方案不唯一,任何满足条件的方案均可)

输入样例 2

4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

输出样例 2

NO

数据范围

  • 1≤n≤2001 \le n \le 200
  • 1≤m≤102001 \le m \le 10200
  • 1≤a,b≤n1 \le a, b \le n
  • 0≤c≤d≤100000 \le c \le d \le 10000