#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
#include <cctype>
#define x first
#define y second
const int NMAX = 1000;
using namespace std;
vector <int> G[NMAX + 5], c[NMAX + 5], nc[NMAX + 5];
vector <int> T[NMAX + 5];
stack <pair <int, int> > st;
int low[NMAX + 5], dfn[NMAX + 5], t[NMAX + 5], comp, ord, root, rootc;
bool a[NMAX + 5][NMAX + 5];

char buffer[1 << 17];
int sz = (1 << 17) , crs = (1 << 17);
void get_int(int &n)
{
    for( ; crs < sz && !isdigit(buffer[crs]) ; crs ++);
    if(crs == sz)
    {
        fread(buffer , sz , 1 , stdin);
        crs = 0;
        for( ; crs < sz && !isdigit(buffer[crs]) ; crs ++);
    }
    n = 0;
    for( ; crs < sz && isdigit(buffer[crs]) ; crs ++)
        n = n * 10 + buffer[crs] - '0';
    if(crs == sz)
    {
        fread(buffer , sz , 1 , stdin);
        crs = 0;
        for( ; crs < sz && isdigit(buffer[crs]) ; crs ++)
            n = n * 10 + buffer[crs] - '0';
    }
}
void comp_biconexe(int u, int v)
{
    pair <int, int> temp;
    comp ++;
    do
    {
        temp = st.top();
        st.pop();
        c[comp].push_back(temp.y);
        nc[temp.y].push_back(comp);
    }
    while(!st.empty() && (u != temp.x || v != temp.y));
    c[comp].push_back(temp.x);
    nc[temp.x].push_back(comp);
}
void dfs(int u)
{
    int v, i;
    dfn[u] = low[u] = ++ ord;
    for(i = 0 ; i < G[u].size() ; i ++)
    {
        v = G[u][i];
        if(!dfn[v])
        {
            t[v] = u;
            st.push({u, v});
            if(u == root)
                rootc ++;
            dfs(v);
            if(dfn[u] <= low[v])
                comp_biconexe(u, v);
            low[u] = min(low[u], low[v]);
        }
        else
        {
            if(v != t[u])
                low[u] = min(low[u], dfn[v]);
        }
    }
}
int cnt, viz[NMAX + 5], vizc[NMAX + 5];
void build(int cmp, int nod_tree)
{
    int v, i, j, new_nod;
    vizc[cmp] = 1;
    for(i = 0 ; i < c[cmp].size() ; i ++)
    {
        v = c[cmp][i];
        if(!viz[v])
        {
            viz[v] = 1;
            new_nod = ++ cnt;
            T[nod_tree].push_back(new_nod);
            for(j = 0 ; j < nc[v].size() ; j ++)
                if(!vizc[nc[v][j]])
                    build(nc[v][j], new_nod);
        }
    }
}
void afisare()
{
    printf("DA\n%d\n", cnt);
    for(int i = 1 ; i <= cnt ; i ++)
        for(int j = 0 ; j < T[i].size() ; j ++)
            printf("%d %d\n", i, T[i][j]);
}
int main()
{
    freopen("linegraph.in", "r", stdin);
    freopen("linegraph.out", "w", stdout);
    int t, n, m, i, j, k, x, y, ok;
    get_int(t);
    root = 1;
    for( ; t ; t --)
    {
        get_int(n);
        get_int(m);
        for(i = 1 ; i <= m ; i ++)
        {
            get_int(x);
            get_int(y);
            G[x].push_back(y);
            G[y].push_back(x);
            a[x][y] = a[y][x] = 1;
        }
        st.push({root, -1});
        dfs(root);
        ok = 1;
        if(ord < n)
            ok = 0;
        for(i = 1 ; i <= comp && ok ; i ++)
            for(j = 0 ; j < c[i].size() && ok ; j ++)
                for(k = j + 1 ; k < c[i].size() && ok ; k ++)
                    ok = a[c[i][j]][c[i][k]];
        for(i = 1 ; i <= n && ok ; i ++)
            if(nc[i].size() > 2)
                ok = 0;
        if(ok == 0)
            printf("NU\n");
        else
        {
            cnt = 1;
            build(1, 1);
            if(m == 0)
            {
                cnt = 2;
                T[1].push_back(2);
            }
            afisare();
        }
        for(i = 1 ; i <= n ; i ++)
            memset(a[i], 0, sizeof(a[i]));
        memset(viz, 0, sizeof(viz));
        memset(vizc, 0, sizeof(vizc));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        for(i = 1 ; i <= n ; i ++)
        {
            G[i].clear();
            nc[i].clear();
        }
        for(i = 1 ; i <= comp ; i ++)
            c[i].clear();
        for(i = 1 ; i <= cnt ; i ++)
            T[i].clear();
        comp = ord = 0;
    }
    return  0;
}