题目链接：https://www.luogu.org/problemnew/show/P3275
把不等式 A > B 转化成 A - B >= 1或者 B - A <= -1再差分约束
B - A 不能是 <= 1
2333
// luogu-judger-enable-o2
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 100000 + 10;
ll n, m, ans, visnum[maxn], dis[maxn];
bool vis[maxn];
struct edge{
ll from, to, next, len;
}e[maxn<<2];
ll head[maxn], cnt;
queue<int> q;
/*struct cmp{
bool operator ()(ll &x, ll &y)
{
return dis[x] < dis[y];
}
};
priority_queue<ll, vector<ll>, cmp> q;*/
inline int read()
{
int k=0,f=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c))
{
k=(k<<1)+(k<<3)+c-48;
c=getchar();
}
return k*f;
}
inline void add(ll u, ll v, ll w)
{
e[++cnt].len = w;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
bool SPFA()
{
while(!q.empty())
{
ll now = q.front();q.pop();
vis[now] = 0;
if(visnum[now] == n-1) return 1;
visnum[now]++;
for(ll i = head[now]; i != -1; i = e[i].next)
{
if(dis[e[i].to] > dis[now] + e[i].len)
{
dis[e[i].to] = dis[now] + e[i].len;
if(!vis[e[i].to])
{
vis[e[i].to] = 1;
q.push(e[i].to);
}
}
}
}
return 0;
}
int main()
{
memset(head, -1, sizeof(head));
//scanf("%lld%lld",&n,&m);
n = read(); m = read();
for(ll i = 1; i <= m; i++)
{
ll opt, u, v;
//scanf("%lld%lld%lld",&opt,&u,&v);
opt = read(); u = read(); v = read();
if(opt == 1)
{
add(u, v, 0);
add(v, u, 0);
}
if(opt == 2)
{
if(u == v)
{
printf("-1\n");
return 0;
}
add(u, v, -1);
}
if(opt == 3)
{
add(v, u, 0);
}
if(opt == 4)
{
if(u == v)
{
printf("-1\n");
return 0;
}
add(v, u, -1);
}
if(opt == 5)
{
add(u, v, 0);
}
}
for(ll i = n; i >= 1; i--)
{
add(0, i, -1);
dis[i] = 0x7fffffff;
}
int s = 0;
q.push(s);
dis[s] = 0; vis[s] = 1;
if(SPFA())
{
printf("-1\n");
return 0;
}
else
{
for(int i = 1; i <= n; i++)
ans += dis[i];
printf("%lld\n",-ans);
return 0;
}
}