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
| #include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int t, n, m, i, j, p[N << 1];
bool valid, vis[N << 1];
char c[9];
vector<int> g[N << 1];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y) {
p[find(x)] = find(y);
}
void dfs(int u, int &s1, int &s2) {
vis[u] = true;
if (u <= n) ++s1;
else ++s2;
for (int v : g[u])
if (!vis[v])
dfs(v, s1, s2);
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n << 1; ++i) {
p[i] = i, vis[i] = false;
g[i].clear();
}
while (m--) {
scanf("%d%d%s", &i, &j, c);
if (*c == 'i') {
merge(i + n, j);
merge(i, j + n);
g[i].emplace_back(j + n);
g[i + n].emplace_back(j);
g[j].emplace_back(i + n);
g[j + n].emplace_back(i);
} else {
merge(i, j);
merge(i + n, j + n);
g[i].emplace_back(j);
g[j].emplace_back(i);
g[i + n].emplace_back(j + n);
g[j + n].emplace_back(i + n);
}
}
valid = true;
for (int i = 1; i <= n; ++i)
if (find(i) == find(i + n)) {
valid = false;
break;
}
if (!valid) printf("-1\n");
else {
int ans = 0;
for (int i = 1, s1 = 0, s2 = 0; i <= n; ++i)
if (!vis[i] && !vis[i + n])
s1 = 0, s2 = 0, dfs(i, s1, s2), ans += max(s1, s2);
printf("%d\n", ans);
}
}
return 0;
}
|