Treat R, G, and B as color \(1\), \(2\), and \(3\), respectively. Split the vertex set into two sets that form a bipartite graph; call the vertices in one of them as left vertices, and the others as right vertices.

The number of times an edge adjacent to vertex \(v\) is removed when its color is \(k\) is fixed. Let \(A_{v, k}\) be this count.

To consider the necessary condition for the existence of a sequence of operations that removes all edges, consider the maximum flow problem on the following graph:

• There are \((3N+2)\) vertices: \(\mathrm{source}, \mathrm{sink}\), and \((v, k)\ (1\leq v\leq N, 1\leq k\leq 3)\).
• For each left vertex \(u\), add an edge from vertex \(\mathrm{source}\) to vertex \((u, k)\ (1\leq k\leq 3)\) of capacity \(A_{u, k}\).
• For each right vertex \(v\), add an edge from vertex \((v, k)\ (1\leq k\leq 3)\) to vertex \(\mathrm{sink}\) of capacity \(A_{v, k}\).
• When there is an edge connecting a left vertex \(u\) and a right vertex \(v\), add an edge of capacity \(1\) between vertices \((u, k_1)\) and \((v, k_2)\ (1\leq k_1\leq 3, 1\leq k_2\leq 3, k_1\neq k_2)\).

If an operation sequence exists, the maximum flow on this graph has a capacity \((N-1)\). (For each removal in the operation sequence, the edge and the colors of its endpoints corresponds to a flow from \(\mathrm{source}\) to \(\mathrm{sink}\). Also, the upper bound of the maximum flow is obviously \(N-1\).)

Conversely, if the maximum flow is \((N-1)\), then there always exists an operation sequence. It is sufficient to show:

• In a maximum flow, suppose that there is a flow from vertex \((u, k_1)\) to vertex \((v, k_2)\) (where \(u\) is a left vertex, \(v\) is a right vertex, and \((1\leq k_1\leq 3, 1\leq k_2\leq 3, k_1\neq k_2)\).) For each such flow, we impose the following rule: remove edge \((u,v)\) when vertex \(u\) has color \(k_1\) and vertex \(v\) has color \(k_2\). Then there exists an operation sequence that obeys all these rules.

By induction on \(N\), it is sufficient to show that at least one of the rules can be fulfilled as the first operation. We prove it by contradiction.

For the reconstruction, we may consume \(O(N)\) time to inspect which edge is currently removable, as it costs only a total of \(O(N^2)\) time. The cost of computing flow is also \(O(N^2)\).

from atcoder.maxflow import MFGraph


def solve():
    n = int(input())
    c = [0 if i == "R" else 1 if i == "G" else 2 for i in input()]
    edge_id = {}
    G = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        edge_id[(a, b)] = edge_id[(b, a)] = i
        G[a].append(b)
        G[b].append(a)

    bipartite = [-1] * n
    bipartite[0] = 0
    mf = MFGraph(3 * n + 2)
    S = 3 * n
    T = S + 1

    stc = [0]
    while stc:
        v = stc.pop()
        cnt = [0] * 3
        tmp = c[v]
        for i in range(len(G[v])):
            cnt[tmp] += 1
            tmp = (tmp + 1) % 3

        for i in range(3):
            if bipartite[v] == 0:
                mf.add_edge(S, 3 * v + i, cnt[i])
            else:
                mf.add_edge(3 * v + i, T, cnt[i])

        if bipartite[v] == 0:
            for u in G[v]:
                for i in range(3):
                    for j in range(3):
                        if i != j:
                            mf.add_edge(3 * v + i, 3 * u + j, 1)

        for u in G[v]:
            if bipartite[u] == -1:
                bipartite[u] = bipartite[v] ^ 1
                stc.append(u)

    f = mf.flow(S, T)
    if f != n - 1:
        print("No")
        return

    op = []
    for e in mf.edges():
        if e.flow == 1 and 0 <= e.src < 3 * n and 0 <= e.dst < 3 * n:
            u, x = e.src // 3, e.src % 3
            v, y = e.dst // 3, e.dst % 3
            op.append((u, x, v, y))

    ans = []
    while op:
        for u, x, v, y in op:
            if c[u] == x and c[v] == y:
                op.remove((u, x, v, y))
                ans.append(edge_id[(u, v)])
                c[u] = (c[u] + 1) % 3
                c[v] = (c[v] + 1) % 3
                break

    print("Yes")
    print(*[i + 1 for i in ans])


for _ in range(int(input())):
    solve()