#include<bits/stdc++.h>

using namespace std;

const int inf  = 0x3f3f3f3f;

const int maxn = 5e2 + ;

vector<pair<int, int> >ANS;

vector<int>Gra[maxn], path[maxn][maxn], X, Y, Left, Right;

char str[maxn];

int g[maxn][maxn], col[maxn], *pairr, pairr1[maxn], pairr2[maxn];

int mp[maxn][maxn], lx[maxn], ly[maxn], linker[maxn], slack[maxn];

int n, m, l, nx, ny;

bool vis[maxn], visx[maxn], visy[maxn];

bool DFS(int x){

    visx[x] = true;

    for(int y = ; y < ny; y++) {

        if(visy[y])

            continue;

        int tmp = lx[x] + ly[y] - mp[x][y];

        if(tmp == ) {

            visy[y] = true;

            if(linker[y] == - || DFS(linker[y])) {

                linker[y] = x;

                return true;

            }

        } else if(slack[y] > tmp)

            slack[y] = tmp;

    }

    return false;

}

int KM(){

    memset(linker,-,sizeof(linker));

    memset(ly,,sizeof(ly));

    for(int i = ; i < nx; i++) {

        lx[i] = -inf;

        for(int j = ; j < ny; j++)

            if(mp[i][j] > lx[i])

                lx[i] = mp[i][j];

    }

    for(int x = ; x < nx; x++) {

        for(int i = ; i < ny; i++)

            slack[i] = inf;

        while(true) {

            memset(visx,false,sizeof(visx));

            memset(visy,false,sizeof(visy));

            if(DFS(x))

                break;

            int d = inf;

            for(int i = ; i < ny; i++)

                if(!visy[i] && d > slack[i])

                    d = slack[i];

            for(int i = ; i < nx; i++)

                if(visx[i])

                    lx[i] -= d;

            for(int i = ; i < ny; i++) {

                if(visy[i])

                    ly[i] += d;

                else

                    slack[i] -= d;

            }

        }

    }

    int res = ;

    for(int i = ; i < ny; i++)

        if(linker[i] != -)

            res -= mp[linker[i]][i];

    return res;

}

void getMinRoad(int u){

    queue<int>que;while(!que.empty())que.pop();

    que.push(u);g[u][u] = ;

    path[u][u].push_back(u);

    memset(vis, false, sizeof(vis));

    vis[u] = true;

    while(!que.empty()){

        int st = que.front();que.pop();

        for(auto to : Gra[st]){

            if(vis[to]) continue;

            vis[to] = true;

            g[u][to] = g[u][st] + ;

            path[u][to] = path[u][st];

            path[u][to].push_back(to);

            que.push(to);

        }

    }

}

bool color(int st){

    queue<int> que;while(!que.empty())que.pop();

    X.push_back(st);

    que.push(st);

    col[st] = ;

    while(!que.empty()){

        int u = que.front();que.pop();

        for(auto v : Gra[u]){

            if(col[v] == col[u]) return false;

            if(col[v] != -) continue;

            col[v] = col[u] ^ ;

            if(col[v]) Y.push_back(v);

            else X.push_back(v);

            que.push(v);

        }

    }

    return true;

}

void GetAns(int u, int v, int setp){

    if(u == v) return ;

    vector<int>&tmp = path[u][v];

    for(int i = ; i < tmp.size() - ; i ++)

    if(str[tmp[i]] != str[tmp[i +]]){

        ANS.push_back(make_pair(tmp[i], tmp[i + ]));

        swap(str[tmp[i]], str[tmp[i + ]]);

        GetAns(u, tmp[i], setp + );

        GetAns(tmp[i + ], v, setp + );

        return ;

    }

}

int getSum(vector<int>A, vector<int>B, int Pair[]){

    Left.clear(); Right.clear();

    for(auto x : A) if(str[x] == '') Left.push_back(x);

    for(auto x : B) if(str[x] == '') Right.push_back(x);

    nx = ny = Left.size();

    for(int i = ; i < nx; i ++)

        for(int j = ; j < ny; j ++)

            mp[i][j] = - g[Left[i]][Right[j]];

    int ret = KM();

    for(int i = ; i < nx; i ++){

        int u = Right[i], v = Left[linker[i]];

        Pair[u] = v;Pair[v] = u;

    }

    return ret;

}

bool solve(int st){

    int zero = , sum1 = inf, sum2 = inf;

    X.clear(), Y.clear();

    if(!color(st)) return ;

    for(auto x : X) if(str[x] == '') zero ++;

    for(auto x : Y) if(str[x] == '') zero ++;

    if(zero == X.size()) sum1 = getSum(X, Y, pairr1);

    if(zero == Y.size()) sum2 = getSum(Y, X, pairr2);

    if(sum1 == inf && sum2 == inf) return false;

    pairr = sum1 > sum2 ? pairr2 : pairr1;

    for(auto x : X) if(pairr[x] != -) GetAns(x, pairr[x], );

    return true;

}

void init(){

    memset(pairr1, -, sizeof(pairr1));

    memset(pairr2, -, sizeof(pairr2));

    memset(slack, , sizeof(slack));

    for(int i = ; i <= n; i ++){

        Gra[i].clear();

        col[i] = -;

        for(int j = ; j <= n; j ++){

            g[i][j] = inf;

            path[i][j].clear();

        }

    }

    ANS.clear();

}

int main(){

    int T,a,b;scanf("%d",&T);

    while(T --){

        scanf("%d%d%s", &n, &m, str + );

        init();

        for(int i = ; i < m; i ++){

            scanf("%d%d",&a,&b);

            Gra[a].push_back(b);

            Gra[b].push_back(a);

        }

        for(int i = ; i <= n; i ++) getMinRoad(i);

        bool flag = true;

        for(int i = ; i <= n; i ++){

            if(col[i] == - && !solve(i)){

                flag = false;break;

            }

        }

        if(!flag){

            printf("-1\n");

            continue;

        }

        printf("%d\n", ANS.size());

        for(int i = ; i < ANS.size(); i ++){

            printf("%d %d\n",ANS[i].first, ANS[i].second);

        }

    }

    return ;

}