#1196333 (C++23) No.3784 01 Walk

• 問題: No.3784 01 Walk
• ユーザー: yuki4869.
• 提出日時: 2026-11-01 02:58:43
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 20,372 bytes
• コンパイル時間: 8,341 ms
• コンパイル使用メモリ: 410,744 KB
• 実行使用メモリ: 133,708 KB
• 最終ジャッジ日時: 2026-11-01 02:59:59
• 合計ジャッジ時間: 15,608 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	TLE * 1 -- * 39

ソースコード

// https://github.com/yuki-4869/Algorithm/blob/main/template.cpp
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std; using namespace atcoder;
using ll=long long; using LL=__int128; using mint=modint998244353;
using ld = long double;
using pll=pair<ll,ll>; using tu=tuple<ll,ll,ll>; using tu4 = tuple<ll,ll,ll,ll>;using vl=vector<ll>; using vb=vector<bool>; using vvb=vector<vb>; using vvl=vector<vl>; using vs=vector<string>; using vld=vector<long double>; using vc=vector<char>; using vmi=vector<mint>; using vp = vector<pll>; using vt = vector<tu>;using graph = vvl; using Graph = vector<vp>;
template<class T=ll> auto vec2(ll n,ll m,T x=T()){return vector(n,vector<T>(m,x));} template<class T=ll> auto vec3(ll n,ll m,ll l,T x=T()){return vector(n,vector(m,vector<T>(l,x)));}
template<class T=ll> auto vec4(ll a,ll b,ll c,ll d,T x=T()){return vector(a,vector(b,vector(c,vector<T>(d,x))));}
template<class T> using rpq=priority_queue<T,vector<T>,greater<T>>; // 小さい順priority_queue
using inverse_priority_queue=rpq<ll>;
const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define Re(n) for(ll i = 0; i<(ll)(n);i++)
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++)
#define pb push_back
#define p(s) cout<<(s)<<'\n'
#define p2(s,t) cout<<(s)<<" "<<(t)<<'\n'
#define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n'
#define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n'
#define pe(s) cout<<(s)<<endl
#define pld(...) ([](const auto&... values)->std::ostream&{auto flags=std::cout.flags();auto precision=std::cout.precision();std::cout<<std::fixed<<std::setprecision(12);size_t i=0;((std::cout<<(i++?" ":"")<<static_cast<long double>(values)),...);std::cout<<'\n';std::cout.flags(flags);std::cout.precision(precision);return std::cout;}(__VA_ARGS__))
#define pld2(s,t) pld((s),(t))
#define pld3(s,t,u) pld((s),(t),(u))
#define pld4(s,t,u,v) pld((s),(t),(u),(v))
#define pe2(s,t) cout<<(s)<<" "<<(t)<<endl
#define pe3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<endl
#define pe4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<endl
#define pval(s) cout<<(s).val()<<'\n'
#define Sort(A) sort(all(A))
#define RSort(A) sort(rall(A))
#define p_yes() p("Yes")
#define p_no() p("No")

template<class T> inline ll sz(const T& x){return (ll)x.size();} // サイズ取得
ostream& operator<<(ostream& os,const mint& x){return os<<x.val();} // mint出力
istream& operator>>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力
template<class T> inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新
template<class T> inline bool chmax(T& a,const T& b){if(a<b){a=b; return true;} return false;} // 最大値更新
template<class T,class U> ll LB(const vector<T>& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex
template<class T,class U> ll UB(const vector<T>& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex
template<class T> T vec_min(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return *min_element(all(v));} // vectorの最小値
template<class T> T vec_max(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return *max_element(all(v));} // vectorの最大値
template<class T> T vec_sum(const vector<T>& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和

template<class T=ll> vector<T> cin_vl(ll n){vector<T> ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll
template<class T=ll> vector<vector<T>> cin_vvl(ll h,ll w){vector<vector<T>> ret(h,vector<T>(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll
template<class T=ll> pair<vector<T>,vector<T>> cin_xy(ll n){vector<T> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll
template<class T=ll> tuple<vector<T>,vector<T>,vector<T>> cin_xyz(ll n){vector<T> x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll
template<class T=ll> vector<vector<T>> Cin_vl(ll n,ll k){vector<vector<T>> ret(k,vector<T>(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll
template<class T=ll> vector<pair<T,T>> cin_pairs(ll n){vector<pair<T,T>> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll
template<class T=ll> vector<tuple<T,T,T>> cin_tuples(ll n){vector<tuple<T,T,T>> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll

template<class T> void cout_vl(const vector<T>& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout<<sep; cout<<a[i];} cout<<end;} // vector出力
template<class T> void cout_ver(const vector<T>& a){for(const auto& value:a) cout<<value<<'\n';}
template<class T> void Cout_vl(const vector<T>& a,const vector<T>& b){rep(i,sz(a)) cout<<a[i]<<" "<<b[i]<<'\n';} // 2vector縦出力
template<class T> void cout_vvl(const vector<vector<T>>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力
template<class T=ll> void Swap(vector<vector<T>>& v,ll& h,ll& w){vector<vector<T>> ret(w,vector<T>(h));rep(i,h) rep(j,w) ret[j][i]=v[i][j];v.swap(ret);swap(h,w);} // h*w行列をw*h行列に変換 hとwを自動でswap

ll ceil_div(ll a,ll b){do { if (!(b!=0)) std::abort(); } while (false); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算
ll floor_div(ll a,ll b){do { if (!(b!=0)) std::abort(); } while (false); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算
ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n))
template<class T> vector<T> sort_unique_vec(vector<T> v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector
template<class T> vector<ll> compress(const vector<T>& v){auto xs=sort_unique_vec(v); vector<ll> ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列
template<class T> vector<T> prefix_sum(const vector<T>& v){vector<T> s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和
template<class T> vector<vector<T>> prefix_sum2(const vector<vector<T>>& a){int h=sz(a),w=sz(a[0]); vector<vector<T>> s(h+1,vector<T>(w+1,0)); rep(i,h)rep(j,w)s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+a[i][j]; return s;} // 2次元累積和
template<class T> T range_sum(const vector<T>& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和
template<class T> vector<pair<T,ll>> run_length(const vector<T>& v){vector<pair<T,ll>> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮
vector<pair<char,ll>> run_length(const string& s){vector<pair<char,ll>> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮
template<class T> ll argmin(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return min_element(all(v))-v.begin();} // 最小値のindex
template<class T> ll argmax(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return max_element(all(v))-v.begin();} // 最大値のindex
template<class T> bool in_vec(const vector<T>& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか

bool even(ll x){return x%2==0;}
bool odd(ll x){return x%2!=0;}
ll grid_id(ll x,ll y,ll w){return x*w+y;} // 座標からGridのID
pll grid_xy(ll id,ll w){return {id/w,id%w};} // GridのIDから座標

ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数
ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1
ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗
template<class T> T square(T x){return x*x;} // 二乗
template<class T> void Uni_erase(vector<T>& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除
inline bool OutIn(ll x,ll n){return 0<=x&&x<n;}
inline bool OutIn(ll x,ll y,ll h,ll w){return 0<=x&&x<h&&0<=y&&y<w;}
inline bool OutIn(ll x,ll y,ll z,ll a,ll b,ll c){return 0<=x&&x<a&&0<=y&&y<b&&0<=z&&z<c;} // グリッド範囲内判定
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Random(ll l,ll r){uniform_int_distribution<ll> dist(l,r-1); return dist(rng);} // [l,r)乱数
void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力
vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成
vl vl_N(ll n){vl ret(n); rep(i,n) ret[i]=i+1; return ret;} // 1..nのvector生成
vl dijkstra(const graph& g,const vl& starts){ vl dist(g.size(),inf); queue<ll> q; for(ll s:starts) if(dist[s]==inf){dist[s]=0; q.push(s);} while(!q.empty()){ ll v=q.front(); q.pop(); for(ll to:g[v]) if(dist[to]==inf){dist[to]=dist[v]+1; q.push(to);} } return dist; }
vl dijkstra(const graph& g,ll s){return dijkstra(g,vl{s});}
vl dijkstra(const graph& g,initializer_list<ll> starts){return dijkstra(g,vl(starts));}
vl dijkstra(const Graph& g,const vl& starts){ vl dist(g.size(),inf); rpq<pll> q; for(ll s:starts) if(dist[s]==inf){dist[s]=0; q.push({0,s});} while(!q.empty()){ auto [d,v]=q.top(); q.pop(); if(d!=dist[v]) continue; for(auto [to,w]:g[v]){ if(w>=inf-d) continue; ll nd=d+w; if(nd<dist[to]){dist[to]=nd; q.push({nd,to});} } } return dist; }
vl dijkstra(const Graph& g,ll s){return dijkstra(g,vl{s});}
vl dijkstra(const Graph& g,initializer_list<ll> starts){return dijkstra(g,vl(starts));}
const vl Pow2={1LL,2LL,4LL,8LL,16LL,32LL,64LL,128LL,256LL,512LL,1024LL,2048LL,4096LL,8192LL,16384LL,32768LL,65536LL,131072LL,262144LL,524288LL,1048576LL,2097152LL,4194304LL,8388608LL,16777216LL,33554432LL,67108864LL,134217728LL,268435456LL,536870912LL,1073741824LL,2147483648LL,4294967296LL,8589934592LL,17179869184LL,34359738368LL,68719476736LL,137438953472LL,274877906944LL,549755813888LL,1099511627776LL,2199023255552LL,4398046511104LL,8796093022208LL,17592186044416LL,35184372088832LL,70368744177664LL,140737488355328LL,281474976710656LL,562949953421312LL,1125899906842624LL,2251799813685248LL,4503599627370496LL,9007199254740992LL,18014398509481984LL,36028797018963968LL,72057594037927936LL,144115188075855872LL,288230376151711744LL,576460752303423488LL,1152921504606846976LL};

vl dx={0,1,0,-1}, dy={1,0,-1,0};
vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍

vector<mint> fac,finv,pow2;
void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); pow2.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i; rep1(i,M) pow2[i]=pow2[i-1]*2;} // N+100まで階乗・逆階乗・2の累乗前計算
void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保
mint nCr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[r]*finv[N-r];} // 二項係数
mint nPr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[N-r];} // 順列数

struct SCCResult {
    ll K;
    vl cmp;

    vector<vl> groups;

    graph dag;
    graph rdag;

    vl indeg;
    vl outdeg;

    vb cyclic;

    bool same(ll u, ll v) const {
        return cmp[u] == cmp[v];
    }

    ll size(ll c) const {
        return groups[c].size();
    }

    vl sources() const {
        vl res;
        rep(c,K){
            if(indeg[c] == 0) res.pb(c);
        }
        return res;
    }

    vl sinks() const {
        vl res;
        rep(c,K){
            if(outdeg[c] == 0) res.pb(c);
        }
        return res;
    }

    bool in_cycle(ll v) const {
        return cyclic[cmp[v]];
    }

    bool has_cycle() const {
        for(bool x : cyclic){
            if(x) return true;
        }
        return false;
    }
};

struct WeightedSCCResult : SCCResult {
    vb nonzero_cycle;

    bool has_nonzero_cycle() const {
        for(bool x : nonzero_cycle){
            if(x) return true;
        }
        return false;
    }
};

SCCResult SCCDecomposition(const graph& g){
    ll n = g.size();

    graph rg(n);

    rep(v,n){
        for(auto to : g[v]){
            rg[to].pb(v);
        }
    }

    vl order;
    order.reserve(n);

    vb used(n,false);

    rep(s,n){
        if(used[s]) continue;

        vector<pair<ll,ll>> st;
        st.pb({s,0});

        used[s] = true;

        while(!st.empty()){
            auto &[v,i] = st.back();

            if(i == (ll)g[v].size()){
                order.pb(v);
                st.pop_back();
                continue;
            }

            ll to = g[v][i++];

            if(!used[to]){
                used[to] = true;
                st.pb({to,0});
            }
        }
    }

    vl cmp(n,-1);
    vector<vl> groups;

    ll K = 0;

    for(ll i = n-1; i >= 0; i--){
        ll s = order[i];

        if(cmp[s] != -1) continue;

        groups.pb({});

        vl st = {s};
        cmp[s] = K;

        while(!st.empty()){
            ll v = st.back();
            st.pop_back();

            groups[K].pb(v);

            for(auto to : rg[v]){
                if(cmp[to] == -1){
                    cmp[to] = K;
                    st.pb(to);
                }
            }
        }

        K++;
    }

    graph dag(K), rdag(K);

    vl indeg(K,0);
    vl outdeg(K,0);

    vl seen(K,-1);

    rep(c,K){
        for(auto v : groups[c]){
            for(auto to : g[v]){
                ll d = cmp[to];

                if(c == d) continue;
                if(seen[d] == c) continue;

                seen[d] = c;

                dag[c].pb(d);
                rdag[d].pb(c);

                outdeg[c]++;
                indeg[d]++;
            }
        }
    }

    vb cyclic(K,false);

    rep(c,K){
        if(groups[c].size() >= 2){
            cyclic[c] = true;
        }
    }

    rep(v,n){
        for(auto to : g[v]){
            if(v == to){
                cyclic[cmp[v]] = true;
            }
        }
    }

    return {
        K,
        cmp,
        groups,
        dag,
        rdag,
        indeg,
        outdeg,
        cyclic
    };
}

WeightedSCCResult SCCDecomposition(const Graph& g){
    ll n = g.size();
    graph unweighted(n);

    rep(v,n){
        unweighted[v].reserve(g[v].size());
        for(auto [to,w] : g[v]){
            unweighted[v].pb(to);
        }
    }

    WeightedSCCResult res;
    static_cast<SCCResult&>(res) = SCCDecomposition(unweighted);
    res.nonzero_cycle.assign(res.K,false);

    vector<__int128> potential(n,0);
    vb seen(n,false);

    rep(c,res.K){
        ll root = res.groups[c][0];
        queue<ll> q;
        q.push(root);
        seen[root] = true;

        while(!q.empty()){
            ll v = q.front();
            q.pop();

            for(auto [to,w] : g[v]){
                if(res.cmp[to] != c) continue;
                __int128 next = potential[v] + (__int128)w;

                if(!seen[to]){
                    seen[to] = true;
                    potential[to] = next;
                    q.push(to);
                }
                else if(potential[to] != next){
                    res.nonzero_cycle[c] = true;
                }
            }
        }
    }

    return res;
}

/*
細かい注意点
0-indexed、有向グラフ。無重みはgraph=vector<vector<ll>>。
重み付きはGraph=vector<vector<pair<ll,ll>>>で、辺は{行き先,重み}。重みはllの全範囲。
空グラフ・自己ループ・多重辺に対応。入力は変更しない。構築O(N+M)、メモリO(N+M)。
SCC番号は縮約DAGのトポロジカル順。異なる成分間の辺u->vではcmp[u]<cmp[v]。
縮約DAGの順方向DPは成分番号の昇順、逆方向は降順に処理できる。
cmpは頂点から成分番号、groupsは成分番号から頂点一覧。
重み付き版はWeightedSCCResultを返し、SCCResultの全フィールド・関数も使える。
nonzero_cycle[c]はSCC c に辺重みの総和が0でない有向閉路が存在するか。
正閉路・負閉路の区別はしない。SCC内部の辺だけを使い、__int128のポテンシャルで判定。
dag/rdagは重みを持たない縮約DAG。成分間の多重辺は従来どおり除去する。

使える関数一覧
auto scc = SCCDecomposition(g);  // graphならSCCResult、GraphならWeightedSCCResult O(N+M)

scc.K;                           // 強連結成分の個数
scc.cmp[v];                      // 頂点vが属するSCC番号
scc.same(u,v);                   // u,vが同じSCCか

scc.groups[c];                   // SCC c に属する頂点一覧
scc.size(c);                     // SCC c の頂点数

scc.dag;                         // SCCを縮約したDAG
scc.rdag;                        // 縮約DAGの逆グラフ
scc.indeg[c];                    // SCC c の入次数
scc.outdeg[c];                   // SCC c の出次数

scc.sources();                   // 入次数0のSCC一覧
scc.sinks();                     // 出次数0のSCC一覧

scc.cyclic[c];                   // SCC c が閉路を含むか
scc.in_cycle(v);                 // 頂点vが有向閉路上にあるか
scc.has_cycle();                 // グラフ全体に有向閉路があるか

重み付き版で追加される情報・関数
scc.nonzero_cycle[c];            // SCC c に非0閉路があるか O(1)
scc.has_nonzero_cycle();         // 全体に非0閉路があるか O(K)

基本の関数
graph g={{1},{0,2},{}};
auto scc = SCCDecomposition(g);
auto connected = scc.same(0,1);               // true
auto component = scc.cmp[2];                  // 1
auto sources = scc.sources();                 // 入次数0のSCC一覧
Graph weighted(3);
weighted[0]={{1,2}}; weighted[1]={{0,-1},{2,5}};
auto wscc = SCCDecomposition(weighted);
auto nonzero = wscc.nonzero_cycle[wscc.cmp[0]]; // true: 0 -> 1 -> 0 の重みの和は1
auto any_nonzero = wscc.has_nonzero_cycle();   // true
*/

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll n,m;
    cin >> n >> m;
    Graph g(2*n);
    rep(i,m){
        ll u,v,c;
        cin >> u >> v >> c;
        u--,v--;
        g[u*2].pb({v*2+1,1-c*2});
        g[u*2+1].pb({v*2,c*2-1});
    }

    auto scc = SCCDecomposition(g);
    ll x = scc.K;

    vl Max(2*n,-inf18), Min(2*n,inf18), pt(2*n);
    vb seen(2*n,false);
    vl leader(x);
    leader[scc.cmp[0]] = 0;
    leader[scc.cmp[1]] = 0;
    Max[0] = Min[0] = 0;
    Max[1] = Min[1] = 0;

    
    rep(t,x){
        ll d = leader[t];
        if(d || scc.nonzero_cycle[t]){
            for(auto nt : scc.groups[t]){
                Max[nt] = Inf;
                Min[nt] = -Inf;
                for(auto[ne,c] : g[nt]){
                    leader[scc.cmp[ne]] = 1;
                    Max[ne] = Inf;
                    Min[ne] = -Inf;
                }
            }
        }
        else{
            auto v = scc.groups[t];
            
            queue<ll> q;
            q.push(v[0]);
            seen[v[0]] = true;
            while(!q.empty()){
                auto e = q.front();
                q.pop();
                for(auto [ne,c] : g[e]) if(!seen[ne] && scc.cmp[ne] == t){
                    pt[ne] = pt[e]+c;
                    q.push(ne);
                    seen[ne] = false;
                }
            }
            ll potMax = -inf, potMin = inf;
            rep(i,sz(v)){
                chmax(potMax,Max[v[i]]-pt[v[i]]);
                chmin(potMin,Min[v[i]]-pt[v[i]]);

            }
            for(auto e : v){
                Max[e] = potMax+pt[e];
                Min[e] = potMin+pt[e];
                for(auto[ne,c]:g[e]) if(scc.cmp[ne] != t){
                    chmax(Max[ne],Max[e]+c);
                    chmin(Min[ne],Min[e]+c);
                }

            }
        }

        
    }


    rep(i,n){
        ll ans = max({Max[i*2],-Min[i*2],Max[i*2+1],-Min[i*2+1]});
        if(ans <= Inf9) p(ans);
        else p(-1);
    }
}