#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#define NMAX 100005
#define MMAX 500005
using namespace std;
typedef pair<int,int>pp;
vector<pp>v[NMAX];
int n,T,m,i,j,x,y;
int viz[MMAX],muc[NMAX];
stack<int>st;
void init()
{
    memset(viz,0,sizeof(viz));
    memset(muc,0,sizeof(muc));
    for (i=1;i<=n;++i) v[i].resize(0);
    printf("\n");
}
int main()
{
    freopen("dans.in","r",stdin);
    freopen("dans.out","w",stdout);
    scanf("%d",&T);
    while(T>0)
    {
        --T;
        scanf("%d%d",&n,&m);
        for (i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            v[x].push_back(pp(y,i));
            v[y].push_back(pp(x,i));
            ++muc[x];
            ++muc[y];
        }
    int nr=0,nod=0;
    for(i=1;i<=n;++i)
    {
        if (muc[i]%2==1) ++nr;
        if (muc[i]%2==1) nod=i;
    }
    if (nr>2 || nr==1) printf("NU\n");
    else
    {
        int valid=1;
        st.push(nod);
        int ok=0;
        while(!st.empty())
        {
            x=st.top();
            if (muc[x]==0)
            {
                if (ok==0) {printf("DA\n");ok=1;}
                if (!valid) printf("%d ",x);
                valid=0;
                st.pop();
                continue;
            }
            while(viz[v[x][v[x].size()-1].second]==1)
                v[x].erase(v[x].end()-1);
            viz[v[x][v[x].size()-1].second]=1;
            st.push(v[x][v[x].size()-1].first);
            --muc[x];
            --muc[v[x][v[x].size()-1].first];
            v[x].erase(v[x].end()-1);
        }
    }
    init();
    }
    return 0;
}