be carefull you cann't create a dsu of size 10^9 given becasue max array size limit is roughly 10^7.
hint: you do not need to track all the node parents instead need to track parents of those which only appears in the question.
here is my soulution(c++):
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// priority_queue<type, std::vector<type>, decltype(cmp)> pq(cmp);
// set/multiset<type, decltype(cmp)> s(cmp);
// map<key_type, val_type, decltype(cmp)> m(cmp);
// sort(v.begin(), v.end(), cmp)
// cmp = custom_lamda_compare_function|syntax: [capture](parameters) -> return_type {}
// typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;
using namespace std;
using namespace __gnu_pbds;
using namespace std;
class DSU{
private:
map<int,pair<int, int>> parent;
public:
DSU(int size){}
pair<int, int> find(int node){
if(parent.find(node) == parent.end()){
return {node, -1};
}
return parent[node];
}
bool union_set(int node1, int node2, int p){
auto it = find(node2);
int root = it.first;
int rootP = it.second;
if(rootP == -1){
parent[node2] = {node1, p};
return true;
}
else if(root < node1){
parent[node2] = {node1, p};
return union_set(root, node1 - 1, rootP ^ p);
}
else if(root > node1){
return union_set(node1, root - 1, rootP ^ p);
}
else{
if(rootP == p) return true;
else return false;
}
}
};
int main(){
//////////////////////////////////////////////////////
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//////////////////////////////////////////////////////
int t;
// cin>>t;
// int ct = 0;
t = 1;
while(t--){
while(true){
int n;
cin>>n;
if(n == -1){
break;
}
DSU dsu(n);
int q;
cin>>q;
int ans = 0;
bool b = false;
while(q--){
int x, y, p;
string str;
cin>>x>>y>>str;
p = (str == "even") ? 0 : 1;
bool is = dsu.union_set(x, y, p);
if(is && !b){
ans++;
}
else{
b = true;
}
}
cout<<ans<<'\n';
}
}
}
