bruh

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

//{
//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 1000000007
#define INF 1000000000
//}

int mp;
vector<bool> vis;
vector<int> ord, scc, med;
vector<vector<int>> G, Gt, H;

void dfs1(int u)
{
    vis[u] = true;
    for (int i : G[u])
        if (!vis[i])
            dfs1(i);
    ord.push_back(u);
}

void dfs2(int u, int id)
{
    scc[u] = id;
    for (int i : Gt[u])
        if (!scc[i])
            dfs2(i, id);
}

void dfs3(int u)
{
    vis[u] = true;
    for (int i : H[u])
        if (!vis[i])
            dfs3(i);

    if (H[u].empty())
        mp = u;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T, flag;
    cin >> T >> flag;
    while (T--)
    {
        vis.clear(), ord.clear(), scc.clear(), G.clear(), Gt.clear(), H.clear();

        int N, M;
        cin >> N >> M;

        G.resize(N + 1), Gt.resize(N + 1);
        while (M--)
        {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v), Gt[v].push_back(u);
        }

        vis.resize(N + 1);
        for (int i = 1; i <= N; i++)
            if (!vis[i])
                dfs1(i);

        int csc = 1;
        reverse(ord.begin(), ord.end()), scc.resize(N + 1);
        vector<int> sch = {-1};
        for (int i : ord)
            if (!scc[i])
                sch.push_back(i), dfs2(i, csc), csc++;
        csc--;

        H.resize(csc + 1);
        vector<int> id(csc + 1), od(csc + 1);
        for (int i = 1; i <= N; i++)
            for (int j : G[i])
                if (scc[i] != scc[j])
                    H[scc[i]].push_back(scc[j]), od[scc[i]]++, id[scc[j]]++;

        if (csc == 1)
            cout << "0\n";
        else
        {
            int ca = 0, cb = 0;
            for (int i = 1; i <= csc; i++)
                ca += !id[i], cb += !od[i];
            cout << max(ca, cb) << '\n';

            if (flag)
            {
                vector<pair<int, int>> ans;
                for (int i = 1; i <= csc; i++)
                    vis[i] = false;
                med.clear();
                for (int i = 1; i <= csc; i++)
                    if (!vis[i])
                    {
                        mp = 0, dfs3(i);
                        if (mp)
                            med.push_back(i), med.push_back(mp);
                    }

                for (int i = 1; i < (int)med.size(); i += 2)
                {
                    int a = med[i], b = med[(i + 1) % med.size()];
                    ans.push_back(MP(a, b)), id[b]++, od[a]++;
                }

                int gd = -1;
                list<int> ie, oe;
                for (int i = 1; i <= csc; i++)
                    if (!id[i])
                        ie.push_back(i);
                    else if (!od[i])
                        oe.push_back(i);
                    else
                        gd = i;

                while (!ie.empty() && !oe.empty())
                {
                    int a = ie.front(), b = oe.front();
                    ie.pop_front(), oe.pop_front(), ans.push_back(MP(b, a)), gd = a;
                }

                while (!ie.empty())
                    ans.push_back(MP(gd, ie.front())), ie.pop_front();
                while (!oe.empty())
                    ans.push_back(MP(oe.front(), gd)), oe.pop_front();

                assert(ans.size() == max(ca, cb));
                for (auto p : ans)
                    cout << sch[p.F] << ' ' << sch[p.S] << '\n';
            }
        }
    }

    return 0;
}

//      *****  *****  *   *  *      *****  *   *  *****  *****
//        *   *   *  *   *  *        *    **  *    *    *   *
//       *   *   *  *****  *        *    * * *    *    *****
//   *  *   *   *    *    *        *    *  **    *    *
//  ****   *****    *    *****  *****  *   *    *    *

//     *   *   ***   *   *  **
//    *   *  *   *  *   *  **
//   * * *  *****  *****  **
//  * * *  *   *  *   *
//  * *   *   *  *   *  **