Language: C++

#include <bits/stdc++.h>

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;

constexpr ll MOD = 1000000007LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;

struct CostGraph
{
    using T = ll;
    CostGraph(const int v) : V{v}, edge(v), rev_edge(v) {}
    struct Edge
    {
        Edge(const int from, const int to, const T cost) : from{from}, to{to}, cost{cost} {}
        const int from;
        const int to;
        const T cost;
        bool operator<(const Edge& e) const { return cost != e.cost ? cost < e.cost : to < e.to; }
    };
    void addEdge(const int from, const int to, const T cost)
    {
        edge[from].push_back(Edge{from, to, cost});
        rev_edge[to].push_back(Edge(to, from, cost));
    }
    const int V;
    vector<vector<Edge>> edge;
    vector<vector<Edge>> rev_edge;
};
class StrongConnectedComponent
{
public:
    StrongConnectedComponent(const CostGraph& g)
        : comp_num{0}, size(g.V), comp(size, -1)
    {
        for (int i = 0; i < size; i++) {
            for (const auto& e : g.edge[i]) {
                edge.push_back(make_pair(e.from, e.to));
            }
        }
        vector<int> st;
        vector<bool> used(size, false);
        for (int i = 0; i < size; i++) {
            if (not used[i]) {
                dfs1_scc(g, i, st, used);
            }
        }
        for (int i = 0; i < st.size(); i++) {
            const int s = st[st.size() - i - 1];
            if (comp[s] == -1) {
                dfs2_scc(g, s, comp_num);
                comp_num++;
            }
        }
    }
    const vector<int>& getComp() const { return comp; }
    CostGraph toDAG() const
    {
        CostGraph dag(comp_num);
        for (const auto& e : edge) {
            const int u = comp[e.first];
            const int v = comp[e.second];
            if (u != v) {
                dag.addEdge(u, v, 1);
            }
        }
        return dag;
    }

private:
    void dfs1_scc(const CostGraph& g, const int s, vector<int>& st, vector<bool>& used)
    {
        used[s] = true;
        for (const auto& e : g.edge[s]) {
            if (not used[e.to]) {
                dfs1_scc(g, e.to, st, used);
            }
        }
        st.push_back(s);
    }
    void dfs2_scc(const CostGraph& g, const int s, const int c)
    {
        comp[s] = c;
        for (const auto& e : g.rev_edge[s]) {
            if (comp[e.to] == -1) {
                dfs2_scc(g, e.to, c);
            }
        }
    };
    int comp_num;
    const int size;
    vector<int> comp;
    vector<pair<int, int>> edge;
};
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(e, E) for (const auto& e : E)
#define RESIDUE(s, t) (capacity[s][t] - flow[s][t])
using Weight = ll;
using Array = vector<ll>;
using Matrix = vector<vector<ll>>;
struct Edge
{
    Edge() = default;
    Edge(const int src, const int dst, const ll weight) : src{src}, dst{dst}, weight{weight} {}
    int src;
    int dst;
    ll weight;
};
using Graph = vector<vector<Edge>>;
Graph cutTree(const Graph& g)
{
    int n = g.size();
    Matrix capacity(n, Array(n)), flow(n, Array(n));
    for (int u = 0; u < n; u++) {
        for (const int e : g[u]) {
            capacity[u][e] += e.weight;
        }
    }

    vector<int> p(n), prev;
    vector<Weight> w(n);
    for (int s = 1; s < n; ++s) {
        int t = p[s];  // max-flow(s, t)
        REP(i, n)
        REP(j, n)
        flow[i][j] = 0;
        Weight total = 0;
        while (1) {
            queue<int> Q;
            Q.push(s);
            prev.assign(n, -1);
            prev[s] = s;
            while (!Q.empty() && prev[t] < 0) {
                int u = Q.front();
                Q.pop();
                FOR(e, g[u])
                if (prev[e.dst] < 0 && RESIDUE(u, e.dst) > 0) {
                    prev[e.dst] = u;
                    Q.push(e.dst);
                }
            }
            if (prev[t] < 0) goto esc;
            Weight inc = INF<ll>;
            for (int j = t; prev[j] != j; j = prev[j])
                inc = min(inc, RESIDUE(prev[j], j));
            for (int j = t; prev[j] != j; j = prev[j])
                flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
            total += inc;
        }
    esc:
        w[s] = total;  // make tree
        REP(u, n)
        if (u != s && prev[u] != -1 && p[u] == t)
            p[u] = s;
        if (prev[p[t]] != -1)
            p[s] = p[t], p[t] = s, w[s] = w[t], w[t] = total;
    }
    Graph T(n);  // (s, p[s]) is a tree edge of weight w[s]
    REP(s, n)
    if (s != p[s]) {
        T[s].push_back(Edge(s, p[s], w[s]));
        T[p[s]].push_back(Edge(p[s], s, w[s]));
    }
    return T;
}

// Gomory-Hu tree を用いた最大流 O(n)
Weight maximumFlow(const Graph& T, int u, int t, int p = -1, Weight w = INF<ll>)
{
    if (u == t) return w;
    Weight d = INF<ll>;
    FOR(e, T[u])
    if (e.dst != p)
        d = min(d, maximumFlow(T, e.dst, t, u, min(w, e.weight)));
    return d;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    CostGraph g(N);
    using P = pair<int, int>;
    vector<P> edge(M);
    Graph g_(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g.addEdge(u, v, 1);
        g_[u].push_back(Edge{u, v, 1});
        edge[i] = {u, v};
    }

    const auto tree = cutTree(g_);
    StrongConnectedComponent scc(g);
    const vector<int> comp = scc.getComp();
    for (int i = 0; i < M; i++) {
        const int u = edge[i].first;
        const int v = edge[i].second;
        if (comp[u] != comp[v]) {
            const ll cut = maximumFlow(tree, u, v);
            if (cut > 1) {
                cout << "diff" << endl;
            } else {
                cout << "same" << endl;
            }
        } else {
            const ll cut = maximumFlow(tree, u, v);
            if (cut > 1) {
                cout << "diff" << endl;
            } else {
                cout << "same" << endl;
            }
        }
    }

    return 0;
}


Compiler output:
a.cc: In function 'Graph cutTree(const Graph&)':
a.cc:121:31: error: cannot convert 'const Edge' to 'const int' in initialization
  121 |         for (const int e : g[u]) {
      |                               ^
a.cc:122:33: error: request for member 'weight' in 'e', which is of non-class type 'const int'
  122 |             capacity[u][e] += e.weight;
      |                                 ^~~~~~