不久前,荷马住在一座美丽的城市。有 $$$n$$$ 个区块,编号从 $$$1$$$ 到 $$$n$$$,并且在它们之间有 $$$m$$$ 定向道路。每条道路都有正长度,并且每条道路从索引较小的块到索引较大的块。对于每两个(不同的)街区,它们之间最多只有一条路。
Homer 发现对于两个数字 $$$L$$$ 和 $$$R$$$ 来说,城市是 $$$(L, R)$$$ 连续的。
这座城市被认为是 $$$(L, R)$$$-连续的,如果
1. 从块 $$$1$$$ 到块 $$$n$$$ 的所有路径长度在 $$$L$$$ 和 $$$R$$$ 之间(含);和
2. 对于每一个$$$L \leq d \leq R$$$,从块$$$1$$$到块$$$n$$$只有一条路径,其长度为$$$d$$$。
从块 $$$u$$$ 到块 $$$v$$$ 的路径是一个序列 $$$u = x_0 \to x_1 \to x_2 \to \dots \to x_k = v$$$,其中对于每个 $$$1 \leq i \leq 都有一条从块 $$$x_{i-1}$$$ 到块 $$$x_{i}$$$ 的道路k$$$。路径的长度是路径中所有道路的长度之和。如果 $$$k \neq l$$$ 或 $$$x_i \neq y_i$$$ 对于某些 $$$0 \leq i \leq \min\{k, l\}$$$,则两条路径 $$$x_0 \to x_1 \to \dots \to x_k$$$ 和 $$$y_0 \to y_1 \to \dots \to y_l$$$ 是不同的。
搬到另一个城市后,Homer只记得两个特殊数字$$$L$$$和$$$R$$$,却忘记了街区和道路的数字$$$n$$$和$$$m$$$,以及街区如何通过道路连接。然而,他认为街区数量不应超过$$$32$$$(因为城市很小)。
作为荷马最好的朋友,请告诉他是否有可能找到$$$(L,R)$$$-连续的城市。
输入
单行包含两个整数 $$$L$$$ 和 $$$R$$$ ($$$1 \leq L \leq R \leq 10^6$$$)。
输出
如果无法在 $$$32$$$ 块内找到 $$$(L, R)$$$ 连续城市,请在单行中打印“NO”。
否则,在第一行打印“YES”,后跟 $$$(L, R)$$$ 连续城市的描述。
第二行应包含两个整数 $$$n$$$ ($$$2 \leq n \leq 32$$$) 和 $$$m$$$ ($$$1 \leq m \leq \frac {n(n-1)} 2$$$),其中 $$$n$$$ 表示街区数量,$$$m$$$ 表示道路数量。
然后是 $$$m$$$ 行。 $$$m$$$ 行中的第 $$$i$$$ 应包含三个整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \leq a_i < b_i \leq n$$$) 和 $$$c_i$$$ ($$$1 \leq c_i \leq 10^6$$$) 表示有一条来自街区的有向道路$$$a_i$$$ 阻止长度为 $$$c_i$$$ 的 $$$b_i$$$。
要求每两个街区,连接它们的道路不得超过1条。也就是说,对于每个 $$$1 \leq i < j \leq m$$$,要么 $$$a_i \neq a_j$$$ 要么 $$$b_i \neq b_j$$$。
示例
输入 #1
1 1
输出 #1
YES 2 1 1 2 1
输入 #2
4 6
输出 #2
YES 5 6 1 2 3 1 3 4 1 4 5 2 5 1 3 5 1 4 5 1
注意
在第一个示例中,从块$$$1$$$到块$$$n = 2$$$只有一条路径,其长度为$$$1$$$。
在第二个示例中,从块$$$1$$$到块$$$n = 5$$$有3条路径,分别是长度为$$$4$$$的$$$1 \to 2 \to 5$$$、长度为$$$4$$$的$$$1 \to 3 \to 5$$$和长度为$$$1 \to 4 \to 5$$$的路径$$$6$$$。