#include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=long long; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin>>n>>m; assert(1<=n&&n<=200000); assert(0<=m&&m<=200000); vector>> graph(2*n); vector> validation_graph(n); atcoder::scc_graph g(2*n); set> s; for(int i=0;i>u>>v>>c; assert(!s.count({u,v,c})); s.insert({u,v,c}); assert(1<=u&&u<=n); assert(1<=v&&v<=n); assert(c==1||c==0); u--;v--; graph[u].push_back(make_pair(v+n,2*c-1)); graph[u+n].push_back(make_pair(v,1-2*c)); g.add_edge(u,v+n); g.add_edge(u+n,v); validation_graph[u].push_back(v); } { queue bfs; bfs.push(0); vector seen(n); seen[0]=true; while(!bfs.empty()){ int x=bfs.front(); bfs.pop(); for(int y:validation_graph[x]){ if(!seen[y]){ seen[y]=true; bfs.push(y); } } } for(int i=0;i pot(2*n,inf); vector sccid(2*n,-1); vector bad(k); vector>> biggraph(k); for(int i=0;ibool{ for(auto[y,w]:graph[x]){ if(sccid[y]!=i)continue; if(pot[y]==inf){ pot[y]=pot[x]+w; if(dfs(dfs,y))return true; }else if(pot[y]!=pot[x]+w)return true; } return false; }; if(dfs(dfs,scc[0]))bad[i]=true; } for(int i=0;i reached(k); vector maxdp(k,-inf),mindp(k,inf); reached[sccid[0]]=true; maxdp[sccid[0]]=-pot[0]; mindp[sccid[0]]=-pot[0]; for(int i=0;i