#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
const int N=1005;
const int M=1500;
using namespace std;
struct edge{ int to, cap, rev; };

int level[N];
int iter[N];
vector<edge> G[N];
vector<int> g[N];
stack<int> ans;
int U[N],V[N],d[N];
char C[N];
int n,m,kase,cnt,sum,s,t;
int k1[N][N],k2[N][N];
void add_edge(int from, int to, int cap){
    G[from].push_back({to, cap, G[to].size()});
    G[to].push_back({from, 0, G[from].size()-1});
}

void bfs(int s){
    memset(level, -1, sizeof level);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();que.pop();
        for(int i=0;i<G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap > 0 && level[e.to] < 0){
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f){
    if(v==t)return f;
    for(int &i=iter[v];i<G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap > 0 && level[v] < level[e.to]){
            int d = dfs(e.to,t,min(f, e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s,int t){
    int flow = 0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof iter);
        int f;
        while((f=dfs(s,t,INF))>0){
            flow+=f;
        }
    }
}

void euler(int u){
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(k2[u][v]){
            k2[u][v]--;
            euler(v);
            ans.push(v);
        }
    }
}

void solve(){
    cin >> n >> m;
    s=0,t=n+1;
    memset(k1,0,sizeof k1);
    memset(d,0,sizeof d);
    for(int i=0;i<500;i++)G[i].clear();
    for(int i=1;i<=m;i++){
        cin >> U[i] >> V[i] >> C[i];
        if(C[i]=='U'){
            add_edge(U[i],V[i],1);
            k1[U[i]][V[i]]++;
        }
        d[U[i]]++;d[V[i]]--;
    }
    sum=0;
    for(int i=1;i<=n;i++){
        if(d[i]&1){
            cout << "No euler circuit exist\n";
            return;
        }
        d[i]/=2;
        if(d[i]>0){
            add_edge(s,i,d[i]);
            sum+=d[i];
        } else {
            add_edge(i,t,-d[i]);
        }
    }
    if(sum!=max_flow(s,t)){
        cout << "No euler circuit exist\n";
        return;
    }
    memset(k2,0,sizeof k2);
    for(int i=0;i<500;i++)g[i].clear();
    for(int i=1;i<=m;i++){
        if(C[i]=='D')g[U[i]].push_back(V[i]),k2[U[i]][V[i]]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<G[i].size();j++){
            edge e=G[i][j];
            if(1<=e.to&&e.to<=n&&k1[i][e.to]){
                if(e.cap){
                    g[i].push_back(e.to);
                    k2[i][e.to]++;
                } else {
                    g[e.to].push_back(i);
                    k2[e.to][i]++;
                }
                k1[i][e.to]--;
            }
        }
    }
    while(!ans.empty())ans.pop();
    euler(1);
    ans.push(1);
    while(!ans.empty()){
        cout << ans.top() << " \n"[ans.size()==1];
        ans.pop();
    }
}

int main()
{
    //freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> kase;
    while(kase--){
        solve();
        if(kase)cout << '\n';
    }
    return 0;
}