Construct a Rooted Tree with Ancestor Constraints

You are given two integers \(n\) and \(m\) representing the number of nodes and the number of constraints, respectively. Your task is to construct a rooted tree with \(n\) nodes (nodes are numbered from 1 to \(n\)) that satisfies all the given constraints.

Each of the next \(m\) lines contains three integers \(x\), \(y\), and \(t\). There are two types of constraints:

• If \(t = 1\), then the constraint is \(x\) must be an ancestor of \(y\).
• If \(t = 0\), then the constraint is \(x\) must not be an ancestor of \(y\).

A convenient observation is that if you construct a tree which is simply a chain (a path) then for any permutation \(P = [p_1, p_2, \dots, p_n]\) of the nodes where the first element \(p_1\) is the root and each \(p_i\) (for \(i \ge 2\)) is the child of \(p_{i-1}\), the set of ancestors for \(p_i\) is exactly \(\{p_1, p_2, \dots, p_{i-1}\}\).

Thus, if we choose a permutation \(P\) such that:

• For every constraint \(x\) must be an ancestor of \(y\) (\(t = 1\)), we have \(\mathrm{pos}(x) < \mathrm{pos}(y)\) in \(P\).
• For every constraint \(x\) must not be an ancestor of \(y\) (\(t = 0\)), we have \(\mathrm{pos}(x) > \mathrm{pos}(y)\) in \(P\).

This is equivalent to finding a linear order of the nodes satisfying certain inequalities. In particular, for each constraint, you can interpret it as an ordering condition:

• If \(t = 1\), add an edge from \(x\) to \(y\) (i.e. \(x < y\)).
• If \(t = 0\), add an edge from \(y\) to \(x\) (i.e. \(y < x\)).

Your task is to check if such an ordering exists. If yes, output YES on the first line and then output a valid permutation \(P\) (space‐separated) on the second line. This permutation represents a chain tree: for every \(i \ge 2\), the parent of \(p_i\) is \(p_{i-1}\). If no valid ordering exists, output -1.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (the number of nodes and constraints, respectively). Each of the next \(m\) lines contains three integers \(x\), \(y\), and \(t\), describing a constraint as follows:

• If \(t = 1\), then \(x\) must be an ancestor of \(y\).
• If \(t = 0\), then \(x\) must not be an ancestor of \(y\).

It is guaranteed that \(1 \le x, y \le n\) and \(t \in \{0,1\}\).

outputFormat

If a valid rooted tree exists satisfying all constraints, output YES in the first line, followed by a line with a permutation \(p_1, p_2, \dots, p_n\) of \(\{1, 2, \dots, n\}\) separated by spaces, where the tree is defined as a chain: the root is \(p_1\) and for each \(i \ge 2\), the parent of \(p_i\) is \(p_{i-1}\).

If no valid tree exists, output -1.

sample

3 1
1 2 1

YES
1 2 3

</p>