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
| #include<cstdio>
#define lie() {ans++;continue;}
using namespace std;
int ds[160000];
int find(int a)
{
if(ds[a]==a)return a;
return ds[a]=find(ds[a]);
}
inline void unite(int a,int b)
{
ds[find(a)]=find(b);
}
inline bool same(int a,int b)
{
return find(a)==find(b);
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n*3;i++)
ds[i]=i;
int ans=0;
for(int i=0;i<k;i++)
{
int type,a,b;
scanf("%d %d %d",&type,&a,&b);
a--; b--;
if(a<0 || a>=n || b<0 || b>=n)
lie();
if(type==1)
{
if(same(a,b+n) || same(a,b+n*2))
lie();
unite(a,b);
unite(a+n,b+n);
unite(a+n*2,b+n*2);
}
else
{
if(same(a,b) || same(a,b+n*2))
lie();
unite(a,b+n);
unite(a+n,b+n*2);
unite(a+n*2,b);
}
}
printf("%d",ans);
}
|