1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 200001 5  6 int n, k, cnt; 7 long long ans, dis[N]; 8 int head[N], to[N << 1], val[N << 1], next[N << 1]; 9 bool vis[N];10 11 inline int read()12 {13     int x = 0, f = 1;14     char ch = getchar();15     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;16     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;17     return x * f;18 }19 20 inline void add(int x, int y, int z)21 {22     to[cnt] = y;23     val[cnt] = z;24     next[cnt] = head[x];25     head[x] = cnt++;26 }27 28 inline bool spfa(int u)29 {30     int i, v;31     vis[u] = 1;32     for(i = head[u]; i ^ -1; i = next[i])33     {34         v = to[i];35         if(dis[v] > dis[u] + val[i])36         {37             dis[v] = dis[u] + val[i];38             if(vis[v]) return 0;39             else if(!spfa(v)) return 0;40         }41     }42     vis[u] = 0;43     return 1;44 }45 46 int main()47 {48     int i, j, x, y, z;49     n = read();50     k = read();51     memset(head, -1, sizeof(head));52     for(i = n; i >= 1; i--) add(0, i, -1);53     for(i = 1; i <= k; i++)54     {55         z = read();56         x = read();57         y = read();58         if(z == 1) add(x, y, 0), add(y, x, 0);59         if(z == 2)60         {61             add(x, y, -1);62             if(x == y)63             {64                 puts("-1");65                 return 0;66             }67         }68         if(z == 3) add(y, x, 0);69         if(z == 4)70         {71             add(y, x, -1);72             if(x == y)73             {74                 puts("-1");75                 return 0;76             }77         }78         if(z == 5) add(x, y, 0);79     }80     if(spfa(0))81     {82         for(i = 1; i <= n; i++) ans -= dis[i];83         printf("%lld\n", ans);84     }85     else puts("-1");86     return 0;87 }