#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m; cin >> n >> m;
    string s; cin >> s;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i]; p[i]--;
    }
    vector<array<int, 2>> edg(m);
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        auto& [u, v] = edg[i];
        cin >> u >> v; u--; v--;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    vector<int> ans;
    auto oper = [&](int i) {
        ans.push_back(i + 1);
        auto [u, v] = edg[i];
        swap(p[u], p[v]);
        s[i] ^= '0' ^ '1';
    };

    // build tree
    {
        vector<vector<int>> tr(n);
        vector<bool> vis(n);
        auto DFS = [&](this const auto& DFS, int u) -> void {
            vis[u] = true;
            for (int i : adj[u]) {
                int v = edg[i][0] ^ edg[i][1] ^ u;
                if (!vis[v]) {
                    tr[u].push_back(i);
                    tr[v].push_back(i);
                    DFS(v);
                } else if (s[i] == '1') {
                    oper(i);
                }
            }
        };
        DFS(0);
        adj = tr;
    }

    bool ok = true;
    // solve for tree
    {
        vector<bool> prc(n);
        auto find_path = [&](this const auto& find_path, int u, int tar, int pi) -> bool {
            if (p[u] == tar) {
                return true;
            }
            for (int i : adj[u]) {
                if (i == pi) {
                    continue;
                }
                int v = edg[i][0] ^ edg[i][1] ^ u;
                if (find_path(v, tar, i)) {
                    oper(i);
                    return true;
                }
            }
            return false;
        };
        auto DFS = [&](this const auto& DFS, int u, int pi) -> void {
            for (int i : adj[u]) {
                if (i == pi) {
                    continue;
                }
                int v = edg[i][0] ^ edg[i][1] ^ u;
                DFS(v, i);
            }
            prc[u] = true;
            if (pi == -1) {
                return;
            }
            if (s[pi] == '0') {
                oper(pi);
            }
            if (p[u] == u) {
                int par = edg[pi][0] ^ edg[pi][1] ^ u;
                int oth = -1;
                for (int i : adj[par]) {
                    int v = edg[i][0] ^ edg[i][1] ^ par;
                    if (!prc[v]) {
                        oth = i;
                        break;
                    }
                }
                if (oth == -1) {
                    ok = false;
                    return;
                }
                oper(pi); oper(oth); oper(pi); oper(oth); oper(pi);
            } else {
                find_path(u, u, -1);
            }
            assert(p[u] == u); assert(s[pi] == '0');
        };
        DFS(0, -1);
    }
    if (ok) {
        cout << "YES\n";
        cout << ans.size() << '\n';
        for (int v : ans) {
            cout << v << " ";
        }
        cout << '\n';
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; cin >> t;
    while (t--) {
        solve();
    }
}