#include<bits/stdc++.h>
#define maxn 3000
using namespace std;

vector<pair<int,int>>g[maxn];
int hp[maxn][maxn];
bool v[maxn],o[maxn];

void dfs(int s,int c,int ch,int i1)
{
    hp[s][c]=ch;
    v[c]=true;
    for(pair<int,int> i:g[c])
    {
        if(v[i.first])
        {
            continue;
        }
        if(i1==1)
        {
            dfs(s,i.first,i.second,i1+1);
        }
        else
        {
            dfs(s,i.first,ch^i.second,i1+1);
        }
    }
    v[c]=false;
}

vector <long long int> happy (int N, int Q, vector <int> u, vector <int> v, vector <int> h, vector <int> t, vector <int> l, vector <int> r) {
    for(int i=0;i<u.size();i++)
    {
        g[u[i]].push_back({v[i],h[i]});
        g[v[i]].push_back({u[i],h[i]});
    }

    for(int i=0;i<N;i++)
    {
        dfs(i,i,0,1);
    }

    vector<long long int>hap;
    for(int i=0;i<Q;i++)
    {
        int ha=0;
        for(int j=l[i];j<=r[i];j++)
        {
            if(t[i]==1)
            {
                o[j]=true;
            }
            else
            {
                o[j]=false;
            }
        }

        for(int j=0;j<N-1;j++)
        {
            if(o[j])
            {
                for(int p=j+1;p<N;p++)
                {
                    if(o[p])
                    {
                        ha+=hp[j][p];
                    }
                }
            }

        }
        hap.push_back(ha);
    }
    return {hap};
}
