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';
          }
     }
}