#include cstdio#include cstring#include cstdlib#include algorithmusing namespace std;const int maxn = 100010;struct Relationship int x a b; rmaxn;struct Edge int to next;bool same; 记录该边是否允许两边相等 emaxn1

#include #include #include #include using namespace std;

const int maxn = 100010;

struct Relationship { int type, a, b; } r[maxn];

struct Edge { int to, next; bool same; //记录该边是否允许两边相等 } e[maxn<<1], e2[maxn];

int n, m, num, num2, cnt, head[maxn], head2[maxn], ltk[maxn], dfn[maxn], low[maxn]; int sta[maxn], top, size[maxn], que[maxn], du[maxn], h, tail, candy[maxn]; bool vis[maxn]; long long ans = 0;

void add(int u, int v, bool k) { e[++num].to = v; e[num].same = k; e[num].next = head[u]; head[u] = num; }

void add2(int u, int v, bool k) { du[v]++; e2[++num2].to = v; e2[num2].same = k; e2[num2].next = head2[u]; head2[u] = num2; }

void dfs(int x) { dfn[x] = low[x] = ++cnt; sta[++top] = x; for (int i = head[x]; i; i = e[i].next) { if (!dfn[e[i].to]) { dfs(e[i].to); low[x] = min(low[x],low[e[i].to]); } else if (!ltk[e[i].to]) { low[x] = min(low[x], dfn[e[i].to]); } } if (dfn[x] == low[x]) { ltk[0]++; while (top) { ltk[sta[top]] = ltk[0]; size[ltk[0]]++; if (sta[top--] == x) break; } } }

void Rebuild() { for (int i = 1; i <= n; i++) { for (int j = head[i]; j; j = e[j].next) { if (ltk[i] != ltk[e[j].to]) { add2(ltk[i], ltk[e[j].to], true); } } } for (int i = 1; i <= m; i++) { if (r[i].type == 2) { if (ltk[r[i].a] == ltk[r[i].b]) { printf("-1\n"); exit(0); } else { add2(ltk[r[i].a], ltk[r[i].b], false); } } else if (r[i].type == 4) { if (ltk[r[i].a] == ltk[r[i].b]) { printf("-1\n"); exit(0); } else { add2(ltk[r[i].b], ltk[r[i].a], false); } } } }

void Topsort() { for (int i = 1; i <= ltk[0]; i++) { if (!du[i]) { que[++tail] = i; vis[i] = true; candy[i] = 1; //candy[i]记录i节点每个孩子要多少糖 } } while (h < tail) { int x = que[++h]; for (int i = head2[x]; i; i = e2[i].next) { if (!--du[e2[i].to]) { que[++tail] = e2[i].to; vis[e2[i].to] = true; } if (!e2[i].same) { candy[e2[i].to] = max(candy[e2[i].to], candy[x] + 1); } else { candy[e2[i].to] = max(candy[e2[i].to], candy[x]); } //dp，如果有一条边不允许相等就要+1 } } for (int i = 1; i <= ltk[0]; i++) { if (!vis[i]) { printf("-1\n"); exit(0); } } }

int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &r[i].type, &r[i].a, &r[i].b); if (r[i].type == 1) { add(r[i].a, r[i].b, true); add(r[i].b, r[i].a, true); } else if (r[i].type == 3) { add(r[i].b, r[i].a, true); } else if (r[i].type == 5) { add(r[i].a, r[i].b, true); } } for (int i = 1; i <= n; i++) { if (!dfn[i]) { dfs(i); } } Rebuild(); Topsort(); for (int i = 1; i <= ltk[0]; i++) { ans += (candy[i] * size[i]); //记录答案，记得开long long } printf("%lld\n", ans); return 0;