/**
* author: mamion
* created: Friday 2024-10-18
**/
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include<cpp-dump-main/cpp-dump.hpp>
#define debug(...) cpp_dump(__VA_ARGS__)
CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
#else
#define debug(...)
#endif // LOCAL
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N = 2e4 + 100;
const int zero = N - 2;
const int one = N - 3;
int lab[N];
int find(int u) {
return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
int join(int u, int v) {
u = find(u); v = find(v);
if (u == v) return false;
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
int n, m, k;
struct query {
int u, v; char c;
};
query queries[N];
void reset(int mid) {
lab[zero] = lab[one] = -1;
for (int i = 1; i <= mid; i++)
lab[queries[i].u] = lab[queries[i].v] = -1;
};
bool check(int mid) {
reset(mid);
for (int i = 1; i <= mid; i++) {
int u = queries[i].u, v = queries[i].v; char c = queries[i].c;
if (c == '<') {
join(u, zero);
join(v, one);
}
if (c == '>') {
join(u, one);
join(v, zero);
}
if (c == '=') join(u, v);
}
int z = k - (-lab[find(zero)] - 1);
if (z == 0) return true;
bitset<N> dp1[2], dp2[2];
vector<int> g;
for (int u = 1; u <= n; u++) {
if (lab[u] >= 0) continue;
if (find(u) == find(one)) continue;
if (find(u) == find(zero)) continue;
int a = -lab[u];
g.push_back(a);
}
int f = 0, s = 1;
dp1[f][0] = 1;
for (int a : g) {
dp1[s] = dp1[f] | (dp1[f] << a);
dp2[s] = dp2[f] | (dp2[f] << a) | (dp1[f] & (dp1[f] << a));
swap(f, s);
}
if (dp1[f][z] && dp2[f][z] == 0) return true;
return false;
}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) cin >> queries[i].u >> queries[i].c >> queries[i].v;
if (n == k) {
cout << 0 << '\n';
return;
}
reset(n);
int ans = -1;
for (int l = 1, r = m; l <= r;) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
#else
#define file "name"
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
#endif // LOCAL
int T; T = 1; if (1) cin >> T;
for (int i = 1; i <= T; i++)
{
debug(i);
solve();
}
}
LyoqCiAqICAgIGF1dGhvcjogIG1hbWlvbgogKiAgICBjcmVhdGVkOiBGcmlkYXkgMjAyNC0xMC0xOAoqKi8KCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojaWZkZWYgTE9DQUwKI2luY2x1ZGU8Y3BwLWR1bXAtbWFpbi9jcHAtZHVtcC5ocHA+CiNkZWZpbmUgZGVidWcoLi4uKSBjcHBfZHVtcChfX1ZBX0FSR1NfXykKQ1BQX0RVTVBfU0VUX09QVElPTl9HTE9CQUwobWF4X2xpbmVfd2lkdGgsIDEwMCk7CkNQUF9EVU1QX1NFVF9PUFRJT05fR0xPQkFMKGxvZ19sYWJlbF9mdW5jLCBjcHBfZHVtcDo6bG9nX2xhYmVsOjpmaWxlbmFtZSgpKTsKQ1BQX0RVTVBfU0VUX09QVElPTl9HTE9CQUwoZW5hYmxlX2FzdGVyaXNrLCB0cnVlKTsKI2Vsc2UKI2RlZmluZSBkZWJ1ZyguLi4pCiNlbmRpZiAvLyBMT0NBTAoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiBsb25nIGRvdWJsZSBsZDsKCmNvbnN0IGludCBOID0gMmU0ICsgMTAwOwpjb25zdCBpbnQgemVybyA9IE4gLSAyOwpjb25zdCBpbnQgb25lID0gTiAtIDM7CgppbnQgbGFiW05dOwppbnQgZmluZChpbnQgdSkgewogICAgcmV0dXJuIGxhYlt1XSA8IDAgPyB1IDogbGFiW3VdID0gZmluZChsYWJbdV0pOwp9CmludCBqb2luKGludCB1LCBpbnQgdikgewogICAgdSA9IGZpbmQodSk7IHYgPSBmaW5kKHYpOwogICAgaWYgKHUgPT0gdikgcmV0dXJuIGZhbHNlOwogICAgaWYgKGxhYlt1XSA+IGxhYlt2XSkgc3dhcCh1LCB2KTsKICAgIGxhYlt1XSArPSBsYWJbdl07CiAgICBsYWJbdl0gPSB1OwogICAgcmV0dXJuIHRydWU7Cn0KCmludCBuLCBtLCBrOwpzdHJ1Y3QgcXVlcnkgewogICAgaW50IHUsIHY7IGNoYXIgYzsKfTsKcXVlcnkgcXVlcmllc1tOXTsKCnZvaWQgcmVzZXQoaW50IG1pZCkgewogICAgbGFiW3plcm9dID0gbGFiW29uZV0gPSAtMTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG1pZDsgaSsrKQogICAgICAgIGxhYltxdWVyaWVzW2ldLnVdID0gbGFiW3F1ZXJpZXNbaV0udl0gPSAtMTsKfTsKCmJvb2wgY2hlY2soaW50IG1pZCkgewogICAgcmVzZXQobWlkKTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG1pZDsgaSsrKSB7CiAgICAgICAgaW50IHUgPSBxdWVyaWVzW2ldLnUsIHYgPSBxdWVyaWVzW2ldLnY7IGNoYXIgYyA9IHF1ZXJpZXNbaV0uYzsKICAgICAgICBpZiAoYyA9PSAnPCcpIHsKICAgICAgICAgICAgam9pbih1LCB6ZXJvKTsKICAgICAgICAgICAgam9pbih2LCBvbmUpOwogICAgICAgIH0KICAgICAgICBpZiAoYyA9PSAnPicpIHsKICAgICAgICAgICAgam9pbih1LCBvbmUpOwogICAgICAgICAgICBqb2luKHYsIHplcm8pOwogICAgICAgIH0KICAgICAgICBpZiAoYyA9PSAnPScpIGpvaW4odSwgdik7CiAgICB9CiAgICBpbnQgeiA9IGsgLSAoLWxhYltmaW5kKHplcm8pXSAtIDEpOwogICAgaWYgKHogPT0gMCkgcmV0dXJuIHRydWU7CiAgICBiaXRzZXQ8Tj4gZHAxWzJdLCBkcDJbMl07CiAgICB2ZWN0b3I8aW50PiBnOwogICAgZm9yIChpbnQgdSA9IDE7IHUgPD0gbjsgdSsrKSB7CiAgICAgICAgaWYgKGxhYlt1XSA+PSAwKSBjb250aW51ZTsKICAgICAgICBpZiAoZmluZCh1KSA9PSBmaW5kKG9uZSkpIGNvbnRpbnVlOwogICAgICAgIGlmIChmaW5kKHUpID09IGZpbmQoemVybykpIGNvbnRpbnVlOwogICAgICAgIGludCBhID0gLWxhYlt1XTsKICAgICAgICBnLnB1c2hfYmFjayhhKTsKICAgIH0KICAgIGludCBmID0gMCwgcyA9IDE7CiAgICBkcDFbZl1bMF0gPSAxOwogICAgZm9yIChpbnQgYSA6IGcpIHsKICAgICAgICBkcDFbc10gPSBkcDFbZl0gfCAoZHAxW2ZdIDw8IGEpOwogICAgICAgIGRwMltzXSA9IGRwMltmXSB8IChkcDJbZl0gPDwgYSkgfCAoZHAxW2ZdICYgKGRwMVtmXSA8PCBhKSk7CiAgICAgICAgc3dhcChmLCBzKTsKICAgIH0KICAgIGlmIChkcDFbZl1bel0gJiYgZHAyW2ZdW3pdID09IDApIHJldHVybiB0cnVlOwogICAgcmV0dXJuIGZhbHNlOwp9Cgp2b2lkIHNvbHZlKCkgewogICAgY2luID4+IG4gPj4gbSA+PiBrOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbTsgaSsrKSBjaW4gPj4gcXVlcmllc1tpXS51ID4+IHF1ZXJpZXNbaV0uYyA+PiBxdWVyaWVzW2ldLnY7CgogICAgaWYgKG4gPT0gaykgewogICAgICAgIGNvdXQgPDwgMCA8PCAnXG4nOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIHJlc2V0KG4pOwoKICAgIGludCBhbnMgPSAtMTsKICAgIGZvciAoaW50IGwgPSAxLCByID0gbTsgbCA8PSByOykgewogICAgICAgIGludCBtaWQgPSAobCArIHIpIC8gMjsKICAgICAgICBpZiAoY2hlY2sobWlkKSkgewogICAgICAgICAgICBhbnMgPSBtaWQ7CiAgICAgICAgICAgIHIgPSBtaWQgLSAxOwogICAgICAgIH0gZWxzZSBsID0gbWlkICsgMTsKICAgIH0KICAgIGNvdXQgPDwgYW5zIDw8ICdcbic7Cn0KCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CgojaWZkZWYgTE9DQUwKICAgIGZyZW9wZW4oIm1haW4uaW5wIiwgInIiLCBzdGRpbik7CiAgICBmcmVvcGVuKCJtYWluLm91dCIsICJ3Iiwgc3Rkb3V0KTsKI2Vsc2UKICAgICNkZWZpbmUgZmlsZSAibmFtZSIKICAgIGlmIChmb3BlbihmaWxlIi5pbnAiLCAiciIpKSB7CiAgICAgICAgZnJlb3BlbihmaWxlIi5pbnAiLCAiciIsIHN0ZGluKTsKICAgICAgICBmcmVvcGVuKGZpbGUiLm91dCIsICJ3Iiwgc3Rkb3V0KTsKICAgIH0KI2VuZGlmIC8vIExPQ0FMCgogICAgaW50IFQ7IFQgPSAxOyBpZiAoMSkgY2luID4+IFQ7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBUOyBpKyspCiAgICB7CiAgICAgICAgZGVidWcoaSk7CiAgICAgICAgc29sdmUoKTsKICAgIH0KfQo=