You are given a weakly connected directed graph~^*~ consisting of ~n~ vertices and ~m~ edges in the form ~u_i \to v_i~ with ~1 \le i \le m~, a binary string ~s~ of length ~m~, and a permutation ~p~ of the values from ~1~ to ~n~. You can perform the following operation zero or more times:

• Choose an index ~i~ from ~1~ to ~m~. Swap the values of ~p_{u_i}~ and ~p_{v_i}~, and simultaneously reverse the direction of the ~i~-th edge of the graph (if the edge is currently ~u_i \to v_i~, it will become ~v_i \to u_i~, and vice versa).

You want to perform the above operations until both of the following conditions are satisfied:

• The permutation ~p~ satisfies ~p_i = i~ for all ~1 \le i \le n~.

• For every edge ~u_i \to v_i~ (~1 \le i \le m~) in the original graph, if ~s_i = \mathtt{0}~, then this edge is not reversed; otherwise, this edge is reversed.

You need to determine whether there exists a sequence of operations that satisfies the two conditions above. If so, find such a sequence of operations with a maximum of ~4n^2~ operations.

————————————

~^*~ A directed graph is called weakly connected if and only if replacing all directed edges ~u \to v~ of the graph with undirected edges ~(u, v)~ results in a connected undirected graph.

Input

The first line contains an integer ~t~ (~1 \le t \le 10\,000~) – the number of test cases. The description of each test case is as follows.

The first line contains two integers ~n~ and ~m~ (~2 \le n \le 500, n - 1 \le m \le \frac{n(n-1)}{2}~) — the number of vertices and edges of the graph. It is guaranteed that the given graph is weakly connected.

The second line contains a binary string ~s~ (~|s| = m, s_i \in \{\mathtt{0}, \mathtt{1}\}~).

The third line contains ~n~ integers ~p_1, p_2, \ldots, p_n~ (~1 \le p_i \le n~) which are the elements of the permutation you are given.

For the next ~m~ lines, the ~i~-th line contains two integers ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le n, u_i \neq v_i~) describing the edge ~u_i \to v_i~ in the original graph. It is guaranteed that between any two vertices in the graph, there exists at most one edge between them.

It is guaranteed that the sum of ~n^2~ across all test cases does not exceed ~250\,000~.

Output

For each test case, if there is no sequence of operations that satisfies both conditions as stated, print ~\mathtt{NO}~ on one line. Otherwise,

• On the first line, print ~\mathtt{YES}~.

• On the second line, print ~k~ (~0 \le k \le 4n^2~) which is the number of operations needed.

• On the third line, print ~k~ integers ~i_1, i_2, \dots, i_k~ (~1 \le i_j \le m~) which are the indices on which you will apply the operations. If ~k = 0~, you may choose to print an empty line, or you may not print this line.

It can be proven that with the given limits, if there exists any sequence of operations that satisfies the problem statement, then there also exists a sequence of operations that satisfies the problem statement using at most ~4n^2~ operations.

Scoring

Sample Input 1

4
5 7
0100101
2 4 1 3 5
5 1
2 4
2 3
1 3
4 3
1 4
4 5
5 7
0100101
3 2 1 5 4
5 1
2 4
2 3
1 3
4 3
1 4
4 5
4 6
000000
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4
3 2
11
1 2 3
1 2
2 3

Sample Output 1

YES
5
1 5 7 1 2
NO
YES
0

YES
6
1 2 1 2 1 2

Notes

The six images below illustrate the transformations in the first test case. In each image, the red color indicates the edge that has been reversed, and two elements are swapped in each operation. Additionally, the bold edges indicate those that have been reversed compared to the original graph.