P1020

#include <bits/stdc++.h>

const int N = 2010, M = 80010;
int t, n, m, ans;
int match[N], pre[N];
int head[N], nxt[M << 1], to[M << 1], idx;
int cnt;
int dfn[N], col[N];
struct Disjoint_Union_Set {
    int pa[N];

    int find(int x) {
        return (x == pa[x]) ? pa[x] : (pa[x] = find(pa[x]));
    }
}dsu;
std::queue<int> q;

void add(int u, int v) {
    nxt[idx] = head[u];
    to[idx] = v;
    head[u] = idx;
    ++ idx;
    return;
}
int lca(int x, int y) {
    ++ cnt;
    x = dsu.find(x), y = dsu.find(y);
    while (dfn[x] != cnt) {
        dfn[x] = cnt;
        x = dsu.find(pre[match[x]]);
        if (y) {
            std::swap(x, y);
        }
    }
    return x;
}
void blossom(int x, int y, int z) {
    while (dsu.find(x) != z) {
        pre[x] = y;
        y = match[x];
        if (col[y] == 2) {
            col[y] = 1;
            q.push(y);
        }
        if (x == dsu.find(x)) {
            dsu.pa[x] = z;
        }
        if (y == dsu.find(y)) {
            dsu.pa[y] = z;
        }
        x = pre[y];
    }
    return;
}
int solve(int s) {
    if (((ans + 1) << 1) > n) {
        return 0;
    }
    for (int i = 1; i <= n; ++ i) {
        col[i] = 0;
        dsu.pa[i] = i;
    }
    while (!q.empty()) {
        q.pop();
    }
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i != -1; i = nxt[i]) {
            int y = to[i];
            if (dsu.find(x) == dsu.find(y) || col[y] == 2) {
                continue;
            }
            if (col[y] == 0) {
                col[y] = 2;
                pre[y] = x;
                if (match[y] == 0) {
                    for (int j = y, last; j; j = last) {
                        last = match[pre[j]];
                        match[j] = pre[j];
                        match[pre[j]] = j;
                    }
                    return 1;
                }
                col[match[y]] = 1;
                q.push(match[y]);
            } else {
                int z;
                z = lca(x, y);
                blossom(x, y, z);
                blossom(y, x, z);
            }
        }
    }
    return 0;
}

int main(void) {
    scanf("%d", &t);
    while (t --) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) {
            head[i] = -1;
            match[i] = dfn[i] = 0;
        }
        ans = cnt = 0;
        for (int i = 1, inpu, inpv; i <= m; ++ i) {
            scanf("%d%d", &inpu, &inpv);
            add(inpu, inpv);
            add(inpv, inpu);
        }
        for (int i = 1; i <= n; ++ i) {
            if (match[i] == 0) {
                ans += solve(i);
            }
        }
        printf("%d\n", n - ans);
        for (int i = 1; i <= n; ++ i) {
            if (match[i] != 0) {
                if (i < match[i]) {
                    printf("%d %d\n", i, match[i]);
                }
            } else {
                if (head[i] == -1) {
                    puts("ISOLATED VERTEX! IMPOSSIBLE!");
                    exit(0);
                }
                printf("%d %d\n", i, to[head[i]]);
            }
        }
    }

    return 0;
}