Simulating Longest Paths in Modified DAGs

Given a simple directed acyclic graph (DAG) \(G\) with \(n\) vertices, where vertex \(i\) is associated with an unknown positive weight \(w_i\), you are asked to construct a new DAG \(G'\) with at most \(2\times n\) vertices and exactly \(n\) edges. In \(G\) the length of a path is defined as the sum of the vertex weights on that path, while in \(G'\) the length of a path is defined as the sum of the edge weights. For \(G'\) you must "pin" each of its edges a weight taken from the set \(\{w_1, w_2, \ldots, w_n\}\>.

Your construction must satisfy the following very strong condition: for every possible sequence of positive numbers \([w_1, w_2, \ldots, w_n]\), the length of the longest path in \(G\) (i.e. \(\max_{P \subseteq G}\sum_{i\in P} w_i\)) is equal to the length of the longest path in \(G'\) (i.e. \(\max_{Q \subseteq G'}\sum_{e\in Q} w_{f(e)}\), where each edge weight is one of the \(w_i\)).

You are allowed to output any valid construction of \(G'\) (that meets the above requirements) or state that no such graph exists. Note that because each edge in \(G'\) must receive a weight (which is one of the \(w_i\)) and \(G'\) has exactly \(n\) edges, your construction is quite restricted.

Observation: It turns out that a valid \(G'\) can be constructed in the following two cases:

• If \(G\) has no edges at all, then the longest path in \(G\) equals \(\max\{w_1, w_2, \ldots, w_n\}\). In this case you may construct \(G'\) as a collection of \(n\) disjoint edges (using \(2n\) vertices) so that the longest path in \(G'\) is also \(\max\{w_1,\ldots, w_n\}\).
• If \(G\) contains a Hamiltonian path (i.e. a path that visits all \(n\) vertices) then for any positive assignment the longest path in \(G\) is the sum \(w_{p_1}+w_{p_2}+\cdots+w_{p_n}\) (where \(p_1, p_2, \ldots, p_n\) is the vertex order along that path) and you may simply output \(G'\) as a chain (a path on \(n+1\) vertices with \(n\) edges) that uses the same multiset of weights.

For any other structure of \(G\) (in which there is no Hamiltonian path and \(G\) is not edgeless) one can show that the longest path value in \(G\) is determined by the maximum of at least two different linear forms (for instance, for a V‐shaped graph with two incoming edges into a sink, the longest path equals \(w_{sink}+\max(w_{source1}, w_{source2})\)), and hence no single construction with exactly \(n\) edges will work for every possible assignment of positive weights.

Your task is therefore to decide, given \(G\), whether a valid \(G'\) exists and, if so, to output one. In this problem we assume the input graph \(G\) is given in the following format. You are to output your answer in the format described below.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of vertices and edges of \(G\). Each of the following \(m\) lines contains two integers \(u\) and \(v\), denoting a directed edge from \(u\) to \(v\). It is guaranteed that \(G\) is a simple DAG (i.e. no self-loops or multiple edges).

outputFormat

If a valid graph \(G'\) exists, print "YES" in the first line. Then print an integer \(p\) (\(\leq 2n\)) indicating the number of vertices in \(G'\), followed by exactly \(n\) lines each describing one edge of \(G'\). An edge is described by three space-separated integers \(u\), \(v\), and \(i\), which signifies a directed edge from \(u\) to \(v\) with weight \(w_i\). If no valid graph exists, simply output "NO".

sample

2 1
1 2

YES
3
1 2 1
2 3 2