旅行计划 （拓扑+DP板子）传送

小明要去一个国家旅游。这个国家有 NN 个城市，编号为 11 至 NN ，并且有 MM 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 ii 停止。

所以他就需要选择最先到达的城市，并制定一条路线以城市 ii 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。

现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的ii ，都需要你为小明制定一条路线，并求出以城市 ii 为终点最多能够游览多少个城市。

分析：

状态转移和那道最长路有点像，而且权值还是1，反而更简单了 这居然是个绿题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 200005
#define ll long long
ll n,m;
ll head[MAXM];int cnt=0;
ll indgr[MAXN];
ll dp[MAXN];
struct node
{
    int to,next;
}edge[MAXM];
void add_edge(int from,int to)
{
    edge[++cnt].to=to;edge[cnt].next=head[from];head[from]=cnt;
}
void init()
{
    for(int i=1;i<=n;i++) 
    {
        dp[i]=0;
        indgr[i]=0;
    }
}
void build()
{
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add_edge(u,v);
        indgr[v]++;
    }
}
void topp()
{
    queue <int> q;
    for(int i=1;i<=n;i++)
    {
        if(indgr[i]==0)
        {
            dp[i]=1;
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int j=edge[i].to;
            dp[j]=max(dp[j],dp[now]+1);
            indgr[j]--;
            if(indgr[j]==0) q.push(j);
        }
    }
}
void output()
{
    for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
}
void solve()
{
    cin>>n>>m;
    init();
    build();
    topp();
    output();
}


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

神经元（拓扑+DP板子） 传送

一个神经元有一些入边，出边组成。内部有一个阈值 UiU_i 和一个值为 CiC_i 。CiC_i 表示神经元目前的状态，CiC_i 大于0时，神经元会向下传递信息

规定，CiC_i 服从公式：（其中 nn 是网络中所有神经元的数目）

Ci=∑(j,i)∈EWj,iCj−UiC_i=\sum_{(j,i)\in{E}}W_{j,i}C_j-U_i

公式中的 Wj,iW_{j,i}（可能为负值）表示连接 jj 号神经元和 ii 号神经元的边的权值。当 CiC_i 大于 00 时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为

CiC_i 。

分析：

转移方程为：c[j]=c[j]+edge[i].val∗c[now]c[j]=c[j]+edge[i].val*c[now] ，再在入队的时候判断一下 cjc_j 是否大于0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 105
#define MAXM MAXN*MAXN
ll n,m;
ll u[MAXN];//每个节点一开始的阈值
ll c[MAXN];//ci=sum(边权*cj)-ui
int indgr[MAXN];
int outdgr[MAXN];
struct node
{
    int to,next,val;
}edge[MAXM];
int head[MAXM];int cnt;
void add_edge(int from,int to,int val)
{
    edge[++cnt].to=to;edge[cnt].val=val;edge[cnt].next=head[from];head[from]=cnt;
}

void topp()
{
    queue <int> q;
    for(int i=1;i<=n;i++) 
    {
        if(c[i]>0&&indgr[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int j=edge[i].to;
            indgr[j]--;
            c[j]=c[j]+edge[i].val*c[now];
            if(indgr[j]==0) 
            {
                c[j]-=u[j];
                if(c[j]>0) q.push(j);
            }
        }
    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>u[i];
    }
    //ci大于0并且入度数为0就入队
    for(int i=1;i<=m;i++)
    {
        int u,v,val;
        cin>>u>>v>>val;
        add_edge(u,v,val);
        indgr[v]++;
        outdgr[u]++;
    }
    topp();
    vector <pair<int,int>> ans;
    int f=0;
    for(int i=1;i<=n;i++)
    {
        if(outdgr[i]==0&&c[i]>0) 
        {
            f=1;
            ans.emplace_back(make_pair(i,c[i]));
        }
    }
    if(f==0) cout<<"NULL"<<endl;
    else for(auto x:ans) cout<<x.first<<" "<<x.second<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

分割线，高能开始

绿豆蛙的归宿 （期望DP）传送

给出张 nn 个点 mm 条边的有向无环图，起点为 11，终点为 nn，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 kk 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 1k\frac{1}{k} 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

分析：

正推和逆推都可以做，逆推式子要简单点但难想

正推：

对于一条从 xx 到 yy 的边

E(x)=p1x1+p2x2+......+pnxnE(x)=p_1x_1+p_2x_2+......+p_nx_n

E(y)=p1(x1+w)+p2(x2+w)+......+pn(xn+w)=E(x)+∑i=1npi×w≠E(x)+wE(y)=p_1(x_1+w)+p_2(x_2+w)+......+p_n(x_n+w)=E(x)+\sum_{i=1}^np_i\times w \not= E(x)+w

从 11 到 ii ，所有概率和 ii 不为1

dp[i]dp[i] 表示从 11 到 ii 的期望，g[i]g[i] 表示从 11 到 ii 的概率，方程的转移：对于一条从 xx 到 yy 的边

dp[y]=∑i=1indgr[y](dp[x]+edge[i]×g[x])/out[x]dp[y]=\sum_{i=1}^{indgr[y]}(dp[x]+edge[i] \times g[x])/out[x]

逆推：

E(y)=p1x1+p2x2+......+pnxnE(y)=p_1x_1+p_2x_2+......+p_nx_n

E(x)=p1(x1+w)+p2(x2+w)+......+pn(xn+w)=E(y)+∑i=1npi×w=E(y)+wE(x)=p_1(x_1+w)+p_2(x_2+w)+......+p_n(x_n+w)=E(y)+\sum_{i=1}^{n}p_i \times w=E(y)+w

从 ii 到 nn ，所有概率和为1

dp[i]dp[i] 表示从 ii 到 nn 的期望，方程转移：对于一条从 xx 到 yy 的边

dp[x]=∑i=1out[x](dp[y]+edge[i])/out[x]dp[x]=\sum_{i=1}^{out[x]}(dp[y]+edge[i])/out[x]

只给出一种正推的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
vector <int> mp[MAXN];
#define ll long long
double ans=0;
int cnt=0;int head[MAXN];
int indgr[MAXN];
ll n,m;
struct edge
{
    int to,next,from;
    double val;
}edge[MAXN];
void add_cnt(int from,int to,double val)
{
    edge[++cnt].to=to;edge[cnt].val=val;edge[cnt].next=head[from];head[from]=cnt;
}

void topp()
{
    queue <int> q;
    q.push(1);
    while(!q.empty())
    {
        int now=q.front();q.pop();
        cout<<"now: "<<now<<endl;
        double son=mp[now].size();
        cout<<now<<"outdgr: "<<son<<endl;
        for(int i=head[now];i;i=edge[i].next)
        {
            ans=ans+(1.0)/(son+0.0)*edge[i].val+0.0;
            indgr[edge[i].to]--;
            if(indgr[edge[i].to]==0) q.push(edge[i].to);
        }
    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int from,to;
        double val;
        cin>>from>>to>>val;
        add_cnt(from,to,val);
        indgr[to]++;
        mp[from].emplace_back(to);
    }
    topp();
   
    cout<<ans<<endl;
}

int main()
{
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

排序 （拓扑的大型模拟）传送

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 A,B,C,DA,B,C,D 表示A<B,B<C,C<DA<B,B<C,C<D。在这道题中，我们将给你一系列形如 A<BA<B 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

  • 根据前 xx 个关系即可确定这 nn 个元素的顺序
  • 根据前 xx 个关系即发现存在矛盾
  • 根据这 mm 个关系无法确定这 nn 个元素的顺序

分析：

数据范围是真的小，说明我们每建一条边就要进行一次拓扑排序，反正也T不了。

再看三种情况，第一种是有稳定顺序，第二种是出现了环，第三个是无环但也没有稳定的拓扑序。

依次分析

第一个问题，有稳定拓扑序说明拓扑排序的层数是 nn 。也就是说，拓扑的过程中一定能出现一条长度为 nn 的链。我们只要看最大的层数是不是 nn 就可以了。

第二个问题，有没有成环。拓扑排序很容易判断，如果没能成功遍历所有点，就说明存在一个环。

第三个问题，看似很难，实际上就是除了第一种和第二种以外的其他情况。

接下来就开始漫长的模拟。

声明一些变量意义：

originalindgroriginalindgr 表示总的图的入度，indgrindgr为每次单次遍历用的临时入度。

setset ssss 有两个用途，一个是统计当前所有字母去重后的数量，一个是之后在拓扑遍历后用来标记哪些字母已出现过

sumsum 统计单次拓扑遍历过的点，用于判环

ansans 表示单次拓扑的最长链，用于判断是否拥有一个稳定的拓扑序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
#define MAXN 30
#define ll long long
int indgr[MAXN];int original_indgr[MAXN];
vector <int> mp[MAXN];
set <int> ss;//用于获得当前元素个数
ll n,m;
ll sum,ans;//遍历的点的数量和拓扑链的最大层数
struct node
{
    int u;
    ll val;//层数
};
int step;
int have;

void output()
{
    queue <int> q;
    memset(indgr,0,sizeof(indgr));
    for(int i=0;i<26;i++)
    {
        for(auto j:mp[i])
        {
            indgr[j]++;
        }
    }
    for(int i=0;i<26;i++)
    {
        if(indgr[i]==0&&ss.count(i))
        {
            q.push(i);
            cout<<(char)(i+'A');
        }
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(auto j:mp[now])
        {
            indgr[j]--;
            if(indgr[j]==0)
            {
                cout<<(char)('A'+j);
                q.push(j);
            }
        }
    }
    
}

void topp()
{
    queue <node> q;
    for(int i=0;i<26;i++)
    {
        if(indgr[i]==0&&ss.count(i))//首先必须得保证这个字母出现过
        {
            q.push(node{i,1});
            sum++;
        }
    }
    while(!q.empty())
    {
        node now=q.front();q.pop();
        int u=now.u;ll val=now.val;
        for(auto v:mp[u])
        {
            indgr[v]--;
            if(indgr[v]==0)
            {
                sum++;
                q.push(node{v,val+1});
                ans=max(val+1,ans);
            }
        }
    }
    if(ans==n)//最长拓扑链长度为n
    {
        printf("Sorted sequence determined after %d relations: ",step);
        output();
        cout<<".";
        exit(0);
    }
    if(sum!=have)//有环
    {
        printf("Inconsistency found after %d relations.",step);
        exit(0);
    }
    
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        step=i;
        string s;
        cin>>s;
        char a=s[0];char c=s[2];
        mp[a-'A'].emplace_back(c-'A');
        ss.insert(a-'A');ss.insert(c-'A');
        have=ss.size();
        original_indgr[c-'A']++;
        sum=0;ans=0;
        memcpy(indgr,original_indgr,sizeof(original_indgr));
        topp();
    }
    printf("Sorted sequence cannot be determined.");
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

放风筝 （拓扑缩点后DP）传送

总体上就是普通的拓扑DP的意思，但是环可以看做一个节点，且权值为环内所有节点 valuevalue 的和

分析：

去他妈的环，先不管他。如果我们不考虑环的情况，这就是很 白菜 的题目。

我们可以采用拓扑排序的方法，遍历整个图，然后对于每个路径维护一下到当前点的最大距离，顺便维护一下这个路径上的最大值。

有环吗，很简单 , TarjanTarjan 缩点吗。

这道题强连通分量维护的是包含的元素的点权和。

具体亿些细节看代码吧，毕竟写的第一道缩点题，注释都是拉满的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
#define MAXM 500005
ll n,m;
ll value[MAXN];//存放每个原始点的点权
ll key[MAXN];//表示这个点位于哪个强联通分量
vector <int> original_mp[MAXN];//原始图，带环
vector <int> mp[MAXN];//缩点后的图
int indgr[MAXN];//缩点后的入度数
struct node
{
    ll mx;
    ll sum;
}sccc[MAXN];//强联通分量维护两个信息，整个强连通分量的最大值和缩点后的点权
stack <int> s;
int visit[MAXN];//标记是否在栈中
int dfn[MAXN];//第一次遍历得到的时间戳
int low[MAXN];//最小时间戳，用于判断是不是强连通分量的根
int num;//时间戳
int cnt;//强联通分量个数
ll dp[MAXN][2];//0表示到i点的最长路径之和，1表示路径上的最大点权

void tarjan(int x)
{
    num++;//时间加一
    dfn[x]=num;low[x]=num;//记录时间戳
    visit[x]=1;
    s.push(x);//入栈及标记
    for(auto j:original_mp[x])//遍历他的儿子们
    {
        if(dfn[j]==0) 
        {
            tarjan(j);//如果这个儿子的强联通分量没更新过，就更新一下，然后更新x的最小时间戳
            low[x]=min(low[j],low[x]);
        }
        else if(visit[j]==1)//如果已经遍历过了并且在栈中
        {
            low[x]=min(dfn[j],low[x]);
        }
    }
    if(dfn[x]==low[x])//当前这个点是强联通分量的根，那么就维护这个强联通分量
    {
        cnt++;
        int now=-1;
        while(x!=now)
        {
            now=s.top();s.pop();
            visit[now]=0;
            key[now]=cnt;
            sccc[cnt].mx=max(sccc[cnt].mx,value[now]);
            sccc[cnt].sum+=value[now];
        }
    }
}

void build()//缩点，建新图
{
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0) tarjan(i);
    }
    //先维护这张图的所有强连通分量
    //下面开始缩点
    for(int i=1;i<=n;i++)
    {
        for(auto j:original_mp[i])
        {
            if(key[i]==key[j])//原来边中的两个点同属于一个强连通分量，就不连边
            continue;
            //维护缩点后的新图
            mp[key[i]].emplace_back(key[j]);
            indgr[key[j]]++;
        }
    }
}

void topp()
{
    queue <int> q;
    for(int i=1;i<=cnt;i++)
    {
        dp[i][0]=sccc[i].sum;
        dp[i][1]=sccc[i].mx;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(indgr[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(auto next:mp[now])//遍历图
        {
            if(dp[now][0]+sccc[next].sum>dp[next][0])//更新最大路径和
            {
                dp[next][0]=dp[now][0]+sccc[next].sum;
                dp[next][1]=max(sccc[next].mx,dp[now][1]);//更新最大值
            }
            else if(dp[now][0]+sccc[next].sum==dp[next][0])//如果有两条路径和最大的路径
            {
                //最大值选两者中最大的那个（相当于选择了那条路径）
                dp[next][1]=max(dp[now][1],dp[next][1]);
            }
            indgr[next]--;
            if(indgr[next]==0) q.push(next);
        }
    }
}

void output()
{
    int ans=1;
    for(int i=1;i<=cnt;i++)
    {
        if(dp[i][0]>dp[ans][0]||(dp[i][0]==dp[ans][0]&&dp[i][1]>dp[ans][1]))
        {
            ans=i;
        }
    }
    cout<<dp[ans][0]<<" "<<dp[ans][1]<<endl;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>value[i];
        key[i]=i;//初始化，类似于并查集
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        original_mp[u].emplace_back(v);
    }
    build();//缩点建新图
    topp();
    output();
}


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

分糖果 （拓扑缩点，建图的玄妙与精密）传送

输入的第一行是两个整数 NN ，KK 。接下来 KK 行，表示这些点需要满足的关系，每行 333 个数字，XX ，AA ，BB 。

  • 如果 X=1X=1 ， 表示第 AA 个小朋友分到的糖果必须和第 BB 个小朋友分到的糖果一样多；
  • 如果 X=2X=2 ， 表示第 AA 个小朋友分到的糖果必须少于第 BB 个小朋友分到的糖果；
  • 如果 X=3X=3 ， 表示第 AA 个小朋友分到的糖果必须不少于第 BB 个小朋友分到的糖果；
  • 如果 X=4X=4 ， 表示第 AA 个小朋友分到的糖果必须多于第 BB 个小朋友分到的糖果；
  • 如果 X=5X=5 ， 表示第 AA 个小朋友分到的糖果必须不多于第 BB 个小朋友分到的糖果；

输出老师至少需要准备的糖果数量，如果不能满足小朋友们所有要求，输出-1。

分析：

很明显这题还是有环。我们想象以下什么情况会构成环，答案是这个集团内所有人的元素只能是同一个值。

既然这样的话，我们尝试先把所有可能出现糖果相同的边连起来，将这些边标记为 truetrue 然后缩点。这样构成一个有向无环图。

接着加入2类和4类边，并把这些边的标记标记为 falsefalse 。这时候就会出现非法情况了。

  • 2类边和4类边出现自环

  • 后来拓扑排序遍历的过程中出现了环（ 1,3,51,3,5 的情况已经不可能出现环了，说明 2,42,4 的加入让图出现了环）

没有啥大问题后进行一个扑的拓，过程中完成 DPDP 统计出结果

下面声明一些变量的意义：

sccscc 表示强连通分量的个数，sccc[i]sccc[i]维护了各个强连通分量的族群大小和糖果数量

edgeedge中的samesame 表示这条边是否允许两边糖果相同，如果能够相同，转移方程为 sccc[j].candy=max(sccc[j].candy,sccc[now].candy)sccc[j].candy=max(sccc[j].candy,sccc[now].candy) ；否则为

sccc[j].candy=max(sccc[now].candy+1,sccc[j].candy)sccc[j].candy=max(sccc[now].candy+1,sccc[j].candy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 100005
#define ll long long

ll n,m;

struct EDGE
{
    int to,next;
    bool same;//记录该边是否允许两边相等
}original_edge[MAXN],edge[MAXM];
int original_head[MAXM],head[MAXM],original_tot,tot;
void original_add_edge(int from,int to,bool same)
{
    original_tot++;original_edge[original_tot].to=to;original_edge[original_tot].next=original_head[from];original_head[from]=original_tot;
    original_edge[original_tot].same=same;
}
void add_edge(int from,int to,bool same)
{
    tot++;edge[tot].to=to;edge[tot].next=head[from];head[from]=tot;
    edge[tot].same=same;
}

struct relation
{
    int f;int a;int b;
}relation[MAXM];

int scc;//强连通分量个数
int num;//时间戳
int visit[MAXN],low[MAXN],dfn[MAXN],key[MAXN];
stack <int> st;
struct node
{
    ll size=0;//糖果相同的人的数量
    ll candy=0;//糖果的数量
}sccc[MAXN];
int indgr[MAXN];
void tarjan(int x)
{
    num++;
    low[x]=num;dfn[x]=num;
    st.push(x);visit[x]=1;
    for(int i=original_head[x];i;i=original_edge[i].next)
    {
        int j=original_edge[i].to;
        if(dfn[j]==0)
        {
            tarjan(j);
            low[x]=min(low[x],low[j]);
        }
        else if(visit[j]==1)
        {
            low[x]=min(low[x],dfn[j]);
        }
    }
    if(low[x]==dfn[x])
    {
        int now=-1;
        scc++;
        while(now!=x)
        {
            now=st.top();st.pop();
            sccc[scc].size++;
            key[now]=scc;
            visit[now]=0;       
        }
    }
}

void build()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=original_head[i];j;j=original_edge[j].next)
        {
            int jj=original_edge[j].to;
            if(key[i]==key[jj]) continue;
            add_edge(key[i],key[jj],true);
            indgr[key[jj]]++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(relation[i].f==2)
        {
            if(key[relation[i].a]==key[relation[i].b])//之前已经定义为糖果相同，现在又要求糖果不同
            {
                cout<<-1<<endl;
                exit (0);
            }
            add_edge(key[relation[i].a],key[relation[i].b],false);
            indgr[key[relation[i].b]]++;
        }
        else if(relation[i].f==4)
        {
            if(key[relation[i].a]==key[relation[i].b])//之前已经定义为糖果相同，现在又要求糖果不同
            {
                cout<<-1<<endl;
                exit (0);
            }
            add_edge(key[relation[i].b],key[relation[i].a],false);
            indgr[key[relation[i].a]]++;
        }
    }
}

void topp()
{
    queue <int> q;
    for(int i=1;i<=scc;i++)
    {
        if(indgr[i]==0)
        {
            sccc[i].candy=1;
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int j=edge[i].to;
            if(edge[i].same==true)//允许两边糖果数量相等
            {
                sccc[j].candy=max(sccc[j].candy,sccc[now].candy);
            }
            else if(edge[i].same==false)//不允许两个强连通分量糖果相等
            {
                sccc[j].candy=max(sccc[now].candy+1,sccc[j].candy);
            }
            indgr[j]--;
            if(indgr[j]==0) q.push(j);
        }
    }
    for(int i=1;i<=scc;i++)
    {
        if(indgr[i]!=0)//出现了自环
        {
            cout<<-1<<endl;
            exit (0);
        }
    }
}

void output()
{
    ll ans=0;
    for(int i=1;i<=scc;i++) 
    {
        ans=ans+sccc[i].candy*sccc[i].size;
    }
    cout<<ans<<endl;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>relation[i].f>>relation[i].a>>relation[i].b;
        if(relation[i].f==1)//将所有权值相同的点缩成一点
        {
            original_add_edge(relation[i].a,relation[i].b,true);
            original_add_edge(relation[i].b,relation[i].a,true);
        }
        else if(relation[i].f==3)
        {
            original_add_edge(relation[i].b,relation[i].a,true);
        }
        else if(relation[i].f==5)
        {
            original_add_edge(relation[i].a,relation[i].b,true);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0) tarjan(i);
    }
    build();
    topp();
    output();
}   

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}