#include <vector>
#include <iostream>

using ll = long long;
using namespace std;

struct Node
{
    ll after;
    ll before;
    vector<ll> sames;
};

int main()
{
    ll i, a, b, c, m, pm, ni, si, N, M;

    cin >> N >> M;

    vector<vector<ll>> ss(M);

    for(i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        ss[i] = vector<ll> { a, b, c };
    }

    vector<Node> nodes(N + 1);
    vector<pair<ll, ll>> ivs(N + 1);
    vector<ll> w(N + 1);

    for(i = 1; i <= N; i++)
    {
        nodes[i].after = nodes[i].before = -1;
        w[i] = 0;
    }

    for(i = 0; i < M; i++)
    {
        switch(ss[i][0])
        {
            case 1:
            nodes[ss[i][1]].sames.push_back(ss[i][2]);
            nodes[ss[i][2]].sames.push_back(ss[i][1]);
            break;
            case 2:
            nodes[ss[i][1]].after = ss[i][2];
            nodes[ss[i][2]].before = ss[i][1];
            break;
            default:
            break;
        }
    }

    for(i = 1; i <= N; i++)
    {
        if(nodes[i].before == -1)
            break;
    }

    ni = i;
    pm = 0;

    while(true)
    {
        w[ni]++;

        vector<ll> sames { ni };
        si = 0;

        while(si < sames.size())
        {
            for(i = 0; i < nodes[sames[si]].sames.size(); i++)
            {
                if(w[nodes[sames[si]].sames[i]])
                    continue;

                sames.push_back(nodes[sames[si]].sames[i]);
                w[nodes[sames[si]].sames[i]]++;
            }

            si++;
        }

        m = pm + 2 * sames.size();

        for(i = 0; i < sames.size(); i++)
            ivs[sames[i]] = make_pair(i + pm + 1, m - i);

        pm = m;

        if(nodes[ni].after == -1)
            break;
        else
            ni = nodes[ni].after;
    }

    for(i = 1; i <= N; i++)
    {
        if(w[i] != 1)
        {
            cout << "NEM" << endl;
            return 0;
        }
    }

    cout << "IGEN" << endl;

    for(i = 1; i <= N; i++)
        cout << ivs[i].first << ' ' << ivs[i].second << endl;

    return 0;
}