# PerMEXuation solution codechef- You are given an integer NN and a (00-indexed) binary string AA having length N+1N+1. Find any permutation PP of 0,1,2,…,N−10,1,2,…,N−1 (or determine that it does not exist) that satisfies the following conditions for all ii (0≤i≤N0≤i≤N):

## PerMEXuation solution codechef

You are given an integer NN and a (00-indexed) binary string AA having length N+1N+1.

Find any permutation PP of 0,1,2,...,N10,1,2,…,N−1 (or determine that it does not exist) that satisfies the following conditions for all ii (0iN0≤i≤N):

• if Ai=0Ai=0: No contiguous segment of PP has mexmex equal to ii
• if Ai=1Ai=1: There exists at least one contiguous segment of PP that has mexmex equal to ii

If multiple permutations exist that satisfy the given conditions, print any.

Note: mexmex of a segment is the smallest non-negative number that does not occur in that segment.

### Input Format

• The first line contains the number of test cases TT. Description of the test cases follows.
• The first line of each test case contains a single integer NN.
• The second line of each test case contains the binary string AA of length N+1N+1.

### Output Format

For each test case print :

• YesYes if there exists a permutation PP that satisfies the conditions described in the statement, followed by the permutation PP in the next line (If multiple permutations exist that satisfy the given conditions, print any).
• NoNo otherwise.

You may print each character of YesYes and NoNo in uppercase or lowercase (for example, yesyesyEsyEsYESYES will be considered identical).

### Constraints

• 1T1041≤T≤104
• 2N31052≤N≤3⋅105
• |A|=N+1|A|=N+1
• It is guaranteed that the sum of NN over all test cases does not exceed 31053⋅105.

### Sample Input 1

4
2
111
5
110100
5
110101
7
11100111


### Sample Output 1

Yes
0 1
No
Yes
0 2 1 4 3
Yes
0 1 3 4 2 5 6


### Explanation

Test case-1: One of the possible permutations satisfying the given conditions is [0,10,1] because:

• mex([1])=0mex([1])=0. Therefore the condition is satisfied for i=0i=0.
• mex([0])=1mex([0])=1. Therefore the condition is satisfied for i=1i=1.
• mex([0,1])=2mex([0,1])=2. Therefore the condition is satisfied for i=2i=2.

Test case-2: It can be proven that no permutation exists that satisfies the given conditions.

Test case-3: One of the possible permutations satisfying the given conditions is [0,2,1,4,30,2,1,4,3] because:

• mex([2])=0mex([2])=0. Therefore the condition is satisfied for i=0i=0.
• mex([0,2])=1mex([0,2])=1. Therefore the condition is satisfied for i=1i=1.
• There does not exist any segment with mex=2mex=2. Therefore the condition is satisfied for i=2i=2.
• mex([0,2,1])=3mex([0,2,1])=3. Therefore the condition is satisfied for i=3i=3.
• There does not exist any segment with mex=4mex=4. Therefore the condition is satisfied for i=4i=4.
• mex([0,2,1,4,3])=5mex([0,2,1,4,3])=5. Therefore the condition is satisfied for i=5i=5.