1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 using namespace std; 5 6 typedef long long ll; 7 const int MAXN=100010; 8 const int MAXK=200010; 9 10 struct Edge 11 { 12 int next,to; 13 int w; 14 }e[MAXK*2]; 15 int head[MAXN],cnt=0; 16 void addEdge(int x,int y,int z) 17 { 18 ++cnt; 19 e[cnt].next=head[x]; 20 e[cnt].to=y; 21 e[cnt].w=z; 22 head[x]=cnt; 23 return; 24 } 25 26 int n,k; 27 ll dis[MAXN]; 28 int num[MAXN]; 29 bool vis[MAXN]; 30 int q[MAXK*2],_head=1,tail=0; 31 bool SPFA(int s) 32 { 33 for (int i=1;i<MAXN;++i) dis[i]=-1; 34 //queue<int> q; //被卡了! 35 //q.push_back(s); 36 q[++tail]=s; 37 vis[s]=true; 38 dis[s]=0; 39 while (_head<=tail) 40 { 41 //int u=q.back(); 42 int u=q[tail]; 43 //q.pop_back(); 44 tail--; 45 vis[u]=false; 46 for (int i=head[u];i!=0;i=e[i].next) 47 { 48 int v=e[i].to,w=e[i].w; 49 if (dis[u]+w>dis[v]) 50 { 51 dis[v]=dis[u]+w; 52 num[v]=num[u]+1; 53 if (num[v]>n) 54 { 55 printf("-1\n"); 56 exit(0); 57 } 58 if (!vis[v]) 59 { 60 //q.push_back(v); 61 q[++tail]=v; 62 vis[v]=true; 63 } 64 } 65 } 66 } 67 return true; 68 } 69 70 int main() 71 { 72 scanf("%d%d",&n,&k); 73 for (int i=1;i<=k;++i) 74 { 75 int x,u,v; 76 scanf("%d%d%d",&x,&u,&v); 77 if (x==1) addEdge(u,v,0),addEdge(v,u,0); 78 else if (x==2) 79 { 80 if (u==v) {printf("-1\n");return 0;} 81 addEdge(u,v,1); 82 } 83 else if (x==3) addEdge(v,u,0); 84 else if (x==4) 85 { 86 if (u==v) {printf("-1\n");return 0;} 87 addEdge(v,u,1); 88 } 89 else if (x==5) addEdge(u,v,0); 90 } 91 for (int i=1;i<=n;++i) addEdge(0,i,1); //建立超级源点0 92 93 SPFA(0); //判断有无解,求解 94 95 ll ans=0; 96 for (int i=1;i<=n;++i) ans+=dis[i]; 97 printf("%lld\n",ans); 98 99 return 0; 100 }