#include <iostream>
#include <vector>
#include <set>
using namespace std;

int n, k;
vector <int> B(3e4, 0);
vector <vector <int>> T(3e4, vector <int>(2, 1));
vector <vector <int>> t(3e4, vector <int>(2, 1));
vector <int> cur(3e4, 1);

void solve(set <int> s) {
    /*cout << endl << i << "  ";
    for (int l = 1; l <= n; l++) cout << v[l] << " ";
    cout << "  ";
    for (int l = 1; l <= n; l++) cout << cur[l] << " ";*/
    int i = *s.begin(), J = cur[i], j = cur[i];
    vector <set <int>> v(n + 1);
    for (int cnt = 0; cnt < 23000; cnt++) {
        for (int l = 1; l <= n; l++) {
            if (!s.count(l)) continue;
            if (B[cur[l]] != B[j]) {
                s.erase(l);
                v[j].insert(l);
            }
            cur[l] = T[cur[l]][B[j]];
        }
        j = T[j][B[j]];
    }
    j = J;
    for (int cnt = 0; cnt < n; cnt++) {
        if (v[j].empty()) { j = T[j][B[j]]; continue; }
        t[(i - 1) * n + j][1 - B[j]] = ((*v[j].begin()) - 1) * n + cur[*v[j].begin()];
        solve(v[j]);
        v[j].clear();
        j = T[j][B[j]];
    }
}

int test(int A) {
    int a = A, b = 1, cnt = 0;
    for (int i = 0; i < 1e2; i++) {
        int x = B[a], y = B[(b % n ? b % n : n)];
        cout << a << " " << b << "  " << x << " " << y << endl;
        if (x != y) cnt++;
        a = T[a][y]; b = t[b][x];
    }
    if (cnt >= k) cout << A << " ";
    return cnt;
}

bool teszt = 1;

int main() {
    if (teszt) {
        n = 3;
        k = n;
        srand(time(0));
        for (int i = 1; i <= n; i++) {
            B[i] = rand() % 2;
            T[i][0] = rand() % n + 1;
            T[i][1] = rand() % n + 1;
        }
        cout << "bemenet:\n";
        for (int i = 1; i <= n; i++) {
            cout << B[i] << " " << T[i][0] << " " << T[i][1] << endl;
        }
        cout << endl;
    }
    else {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> B[i] >> T[i][0] >> T[i][1];
        cin >> k;
    }
    set <int> s;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            t[(i - 1) * n + j][0] = (i - 1) * n + T[j][0];
            t[(i - 1) * n + j][1] = (i - 1) * n + T[j][1];
        }
        cur[i] = i;
        s.insert(i);
    }
    solve(s);
    cout << n * n << " 1\n";
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << B[j] << " " << t[(i - 1) * n + j][0] << " " << t[(i - 1) * n + j][1] << "\n";
        }
    }

    cout << endl;
    bool jo = true;
    //for (int i = 1; i <= n; i++) if (test(i) >= k) jo = false;
    test(3);
    cout << endl << (jo ? "HELYES" : "ROSSZ");
}

/*

5
1 5 1
1 1 4
0 5 4
0 2 3
0 2 2
5


3
1 2 1
0 1 3
0 2 2
3

*/