← 返回题目列表

Codeforces · 60/C

C. 蘑菇冲突

中文机器翻译题面 查看原题

Pasha 和 Akim 正在制作森林地图 - 草坪是图的顶点,连接草坪的道路是其边缘。他们决定用以下方式对每个草坪上的笑蘑菇的数量进行编码:在两个草坪之间的每条边上写下两个数字,即这些草坪上蘑菇数量的最大公约数(GCD)和最小公倍数(LCM)。但有一天,帕夏和阿基姆因为笑蘑菇的问题发生了争执,并撕毁了地图。帕夏只留下了其中的一部分,仅包含 m 条道路。你的任务是帮助帕夏——使用他拥有的地图来恢复每片草坪上蘑菇的数量。由于结果不一定是唯一的,请帮助帕夏恢复任何一个或报告这种蘑菇排列不存在。保证初始地图上道路的数量不少于1且不超过106。

输入

第一行包含两个数字 n 和 m ($$1 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2}$$),它们是我们所知道的草坪和道路的数量。接下来的 m 行每行包含 4 个数字,分别是道路所连接的草坪数量、这些草坪上蘑菇数量的 GCD 和 LCM(1 ≤ GCD,LCM ≤ 106)。

可以保证,没有道路将草坪与其自身相连,并且没有两个草坪由多于一条的道路连接。

输出

答案应在第一行包含“是”或“否”,说明是否可以执行该安排。如果答案为“是”,则在下一行打印n个数字,即相应草坪上蘑菇的数量。

示例

输入 #1

1 0

输出 #1

YES
1

输入 #2

2 1
1 2 1 3

输出 #2

YES
1 3

输入 #3

3 2
3 2 1 2
3 1 1 10

输出 #3

YES
5 1 2

输入#4

2 1
1 2 3 7

输出#4

NO