记录编号	543281	评测结果	AAAAAAAAAAA
题目名称	激突冲击	最终得分	100
用户昵称	Lovely_Xianshen	是否通过	通过
代码语言	C++	运行时间	0.165 s
提交时间	2019-10-04 09:54:58	内存使用	20.81 MiB

#include<bits/stdc++.h>
#define gcr getchar()
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,k,h[N],net[N],to[N],cnt,w[N],dis[N],tot[N];
bool vis[N];
queue<int>q;

inline int read(){
	int x=0,f=1;
	char ch=gcr;
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=gcr;}
	while(!(ch<'0'||ch>'9')) {x=x*10+ch-'0';ch=gcr;}
	return x*f;
} 

inline void add(int u,int v,int c){
	to[++cnt]=v;
	net[cnt]=h[u];
	h[u]=cnt;
	w[cnt]=c;
}

int main(){
	freopen("gin.in","r",stdin);
	freopen("gin.out","w",stdout);
	n=read();k=read();
	int u,v,f;
	while(k--){
		f=read();u=read();v=read();
		if(f==1) add(u,v,0),add(v,u,0);
		else if(f==2) {
			if(u==v) {cout<<-1;return 0;}
			add(u,v,1);
		}
		else if(f==3)add(v,u,0);
		else if(f==4){
			if(u==v) {cout<<-1;return 0;}
			add(v,u,1);
		}
		else if(f==5) add(u,v,0);
	}
	for(int i=n;i>=1;i--) add(0,i,1);
	vis[0]=1,q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		if(tot[u]==n-1){cout<<-1;return 0;}
		tot[u]++;
		for(int i=h[u];i;i=net[i])
			if(dis[to[i]]<dis[u]+w[i]){
				dis[to[i]]=dis[u]+w[i];
				if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
			}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=dis[i];
	cout<<ans;
	return 0;
}