Temp

#define task ""
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 4e5 + 5;
constexpr int mod = 965914163;
struct dsu
{
    int par[N];
    dsu()
    {
        memset(par, -1, sizeof par);
    }

    int findpar(int v)
    {
        return par[v] < 0 ? v : par[v] = findpar(par[v]);
    }

    void Merge(int u, int v)
    {
        u = findpar(u);
        v = findpar(v);

        if (u == v)
            return;

        if (par[u] < par[v])
            swap(u, v);
        par[v] += par[u];
        par[u] = v;
    }
} f;

int n, m, k, h, val[2];
int u[N], v[N], dp[N];
char c[N];

void Read()
{
    cin >> n >> m >> k;
    h = k + 1;

    for (int i = 1; i <= m; ++i)
        cin >> u[i] >> c[i] >> v[i];
}

void Erase(int v)
{
    for (int i = 0; i + v <= k; ++i)
        dp[i + v] = (dp[i + v] + mod - dp[i]) % mod;
}

void Update(int v)
{
    for (int i = k; ~i; --i)
        dp[i + v] = (dp[i + v] + dp[i]) % mod;
}

void Solve()
{
    if (k == 0 || k == n)
    {
        cout << "0\n";
        return;
    }

    val[0] = n + 1;
    val[1] = n + 2;
    dp[0] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = i - 1; ~j; --j)
            (dp[j + 1] += dp[j]) %= mod;

    for (int i = 1; i <= m; ++i)
    {
        if (c[i] == '<' || c[i] == '>')
        {
            if (c[i] == '>')
                swap(u[i], v[i]);

            if (f.findpar(u[i]) != f.findpar(val[0]))
            {
                k -= -f.par[f.findpar(u[i])];
                Erase(-f.par[f.findpar(u[i])]);
                f.Merge(u[i], val[0]);
            }
            if (f.findpar(v[i]) != f.findpar(val[1]))
            {
                Erase(-f.par[f.findpar(v[i])]);
                f.Merge(v[i], val[1]);
            }
        }
        else if (c[i] == '=')
        {
            if (f.findpar(u[i]) != f.findpar(v[i]))
            {
                if (f.findpar(u[i]) != f.findpar(val[0]) && f.findpar(u[i]) != f.findpar(val[1]))
                    Erase(-f.par[f.findpar(u[i])]);
                if (f.findpar(v[i]) != f.findpar(val[0]) && f.findpar(v[i]) != f.findpar(val[1]))
                    Erase(-f.par[f.findpar(v[i])]);

                f.Merge(u[i], v[i]);
                if (f.findpar(u[i]) != f.findpar(val[0]) && f.findpar(u[i]) != f.findpar(val[1]))
                    Update(-f.par[f.findpar(u[i])]);

                k = h - (-f.par[f.findpar(val[0])]);
            }
        }

        if (dp[k] == 1)
        {
            cout << i << "\n";
            return;
        }
    }

    cout << "-1\n";
}

void Destroy()
{
    for (int i = 1; i <= n + 2; ++i)
        f.par[i] = (dp[i] = 0) - 1;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    int t;
    for (cin >> t; t--;)
    {
        Read();
        Solve();
        Destroy();
    }
}