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

using ll = long long;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int t=rng()%5+1;
    cout<<t<<"\n";
    while(t--)
    {
        int n=rng()%5+2,m=rng()%5;
        vector<int> perm(n);
        iota(all(perm),1);
        shuffle(all(perm),rng);
        vector<pii> edges;
        for(int i=1;i<n;i++)
        {
            int j=rng()%i;
            if(rng()%2)
                edges.pb({perm[i],perm[j]});
            else
                edges.pb({perm[j],perm[i]});
        }
        while(m--)
        {
            int i=rng()%n;
            int j=i;
            while(j==i)
                j=rng()%n;
            edges.pb({perm[i],perm[j]});
        }
        shuffle(all(edges),rng);
        cout<<n<<" "<<edges.size()<<"\n";
        for(auto[x,y]:edges)
            cout<<x<<" "<<y<<"\n";
        while(n--)
            cout<<rng()%5+1<<" ";
        cout<<"\n";
    }
}