#include #define endl '\n' using namespace std; const int MAXN=1e4+5; int n; map m; vector > adj[MAXN]; double d[MAXN]; int par[MAXN]; int num=1; bool neg[MAXN]; bool used[MAXN]; bool Ford_Bellman() { for(int i=1;i<=num;i++) { d[i]=0; par[i]=-1; } d[m["BGN"]]=1; par[m["BGN"]]=m["BGN"]; for(int t=0;td[adj[i][j].first]) { d[adj[i][j].first]=d[i]*adj[i][j].second; par[adj[i][j].first]=i; } } } } bool fl=0; for(int i=1;i<=num;i++) { for(int j=0;jd[adj[i][j].first]) { d[adj[i][j].first]=d[i]*adj[i][j].second; neg[i]=1; neg[adj[i][j].first]=1; fl=1; } } } for(int i=1;i<=num;i++) { if(neg[i]) { int v=i; int u=par[v]; while(u!=v) { neg[u]=1; u=par[u]; } } } if(fl) return 1; return 0; } void dfs(int v) { used[v]=1; for(int i=0;i>n; for(int i=0;i>u>>v>>w; if(!m[u]) m[u]=num++; if(!m[v]) m[v]=num++; adj[m[u]].push_back(make_pair(m[v],w)); } num--; bool fl=Ford_Bellman(); if(!fl) { cout<<"NO"<