tarjan缩点+spfa
我寻思着都缩完点了应该不至于还T吧（
WA on #8-#10 #21-#25 #29-#31
TLE on #26-#28

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#define PII pair<int,int>
using namespace std;

const int N = 100005;
vector<int> g[N];
vector<PII > h[N];

pair<int, PII > p[N];

stack<int> stk;
bool instk[N];
int dfn[N], low[N];
int timestamp, scc_cnt;
int id[N], size[N];

int dis[N], tt[N];
bool vis[N];
queue<int> q;

void add(int x, int y)
{
	g[x].push_back(y);
}

void tarjan(int u)
{
	dfn[u] = low[u] = ++timestamp;
	stk.push(u), instk[u] = true;

	for (int i = 0; i < (int)g[u].size(); i++)
	{
		int pos = g[u][i];
		if (!dfn[pos])
		{
			tarjan(pos);
			low[u] = min(low[u], low[pos]);
		}
		else if (instk[pos])
			low[u] = min(low[u], dfn[pos]);
	}

	if (dfn[u] == low[u])
	{
		int y;
		scc_cnt++;
		do
		{
			y = stk.top();
			stk.pop();
			instk[u] = false;
			id[y] = scc_cnt;
			size[scc_cnt]++;
		}
		while (y != u);
	}
}

bool spfa(int n)
{
	for (int i = 1; i <= n; i++)
		dis[i] = -0x3f3f3f3f;
	dis[0] = 0;

	q.push(0);
	vis[0] = true;

	while (!q.empty())
	{
		int pos = q.front();
		q.pop();
		vis[pos] = false;

		if (tt[pos] > n + 1)
			return true;

		for (int i = 0; i < (int)h[pos].size(); i++)
		{
			int to = h[pos][i].first;
			int val = h[pos][i].second;
			if (dis[to] < dis[pos] + val)
			{
				dis[to] = dis[pos] + val;
				if (!vis[to])
				{
					q.push(to);
					tt[pos]++;
					vis[to] = true;
				}
			}
		}
	}
	return false;
}

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i++)
	{
		int x, a, b;
		scanf("%d%d%d", &x, &a, &b);
		p[i].first = x;
		p[i].second.first = a;
		p[i].second.second = b;
	}

	for (int i = 1; i <= k; i++)
	{
		int x = p[i].second.first, y = p[i].second.second;
		if (p[i].first == 1)
			add(y, x), add(x, y);
		else if (p[i].first == 3)
			add(y, x);
		else if (p[i].first == 5)
			add(x, y);
	}

	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i);

	for (int i = 1; i <= k; i++)
	{
		int x = p[i].second.first, y = p[i].second.second;
		if ((p[i].first == 2 || p[i].first == 4) && id[x] == id[y])
		{
			printf("-1");
			return 0;
		}
		else if (p[i].first == 2)
			h[id[x]].push_back(make_pair(id[y], 1));
		else if (p[i].first == 4)
			h[id[y]].push_back(make_pair(id[x], 1));
	}

	for (int i = 1; i <= scc_cnt; i++)
		h[0].push_back(make_pair(i, 1));

	long long ans = 0;
	if (spfa(scc_cnt))
	{
		printf("-1");
		return 0;
	}
	for (int i = 1; i <= scc_cnt; i++)
		ans += 1ll * dis[i] * size[i];

	printf("%lld", ans);
	return 0;
}