Official

E - lt and le Editorial by en_translator


Relax the conditions and suppose that all conditions have \(t _ i=0\).

Then, for the directed graph \(G\) with \(N\) vertices \(1,2,\ldots,N\) with edges from \(u _ i\) to \(v _ i\) \((1\le i\le Q)\), if it is reachable from \(x\) to \(y\) on \(G\), then \(A _ x\le A _ y\) must hold. In particular, if two vertices \(x\) and \(y\) are in the same connected component of \(G\), then \(A _ x\le A _ y\) and \(A _ x\ge A _ y\), thus \(A _ x=A _ y\) must hold. To the contrary, if two vertices \(x\) and \(y\) are in different connected components of \(G\), then one can always make \(A _ x\ne A _ y\). (This can be achieved by, for example, adding edges between connected component if the original graph has a corresponding edge (and if it is not a self-loop), and assigning numbers in topological order.)

Now let us consider cases where conditions with \(t _ i=1\) exist. In the graph defined likewise, it is still necessary that two vertices \(x\) and \(y\) in the same connected component must satisfy \(A _ x=A _ y\). Therefore, if there are an edge connecting two different vertices in a connected component such that \(t _ i=1\), no sequence satisfies the conditions. To the contrary, if there is no such edge, there always exists an applicable sequence, and the construction above indeed satisfies the conditions.

The time complexity is \(O(N+Q)\).

The following is sample code:

#include <iostream>
#include <vector>
#include <ranges>
#include <atcoder/scc>

int main() {
    using namespace std;
    unsigned N, Q;
    cin >> N >> Q;
    atcoder::scc_graph scc(N);
    vector<pair<unsigned, unsigned>> lt;
    for (unsigned i{}; i < Q; ++i) {
        unsigned t, u, v;
        cin >> t >> u >> v;
        --u;
        --v;
        scc.add_edge(u, v);
        if (t) lt.emplace_back(u, v); // accumulate t = 1 edges
    }

    vector<unsigned> ans(N);
    // Assign numbers in topological order of the connected components
    for (const auto& [i, component] : scc.scc() | views::enumerate)
        for (const auto x : component)
            ans[x] = i + 1;

    // If there is a contradiction
    for (const auto& [u, v] : lt)
        if (ans[u] == ans[v]) {
            cout << "No" << endl;
            return 0;
        }
    cout << "Yes" << endl;
    for (string delim{}; const auto a : ans) cout << a << " ";
    cout << endl;
    return 0;
}