Ti viene dato un albero con $N$ vertici numerati da $1$ a $N$. L'$i$-esimo arco dell'albero collega i vertici $u_i$ e $v_i$. Inizialmente, per ogni $i$ ($1 \le i \le N$), il vertice $i$ contiene una pietra se $A_i = 1$ e nessuna pietra se $A_i = 0$.

Puoi eseguire ripetutamente la seguente operazione:

• Seleziona un arco non ancora scelto avente una pietra su esattamente uno dei suoi estremi, e sposta quella pietra sull'altro estremo.

Determina se è possibile eseguire l'operazione esattamente $N - 1$ volte. Se è possibile, stampa l'ordine in cui vengono selezionati gli archi.

Input

L'input contiene uno o più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^5$), che indica il numero di casi di test. Seguono le descrizioni dei $T$ casi di test, ciascuna nel formato seguente.

$$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned} $$

La prima riga contiene un intero $N$ ($2 \le N \le 2 \times 10^5$) che rappresenta il numero di vertici.

Per ogni $i$ ($1 \le i \le N - 1$), l'$i$-esima delle successive $N - 1$ righe contiene due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le N$) separati da uno spazio, ad indicare che l'$i$-esimo arco collega i vertici $u_i$ e $v_i$. È garantito che il grafo dato sia un albero.

L'ultima riga contiene $N$ interi $A_1, A_2, \ldots, A_N$ ($A_i \in \{0, 1\}$) separati da spazi. $A_i$ indica se inizialmente è presente una pietra sul vertice $i$.

La somma di $N$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ogni caso di test, stampa la risposta come segue.

Se è impossibile eseguire l'operazione esattamente $N - 1$ volte, stampa No su una singola riga.

Se è possibile, stampa Yes sulla prima riga, seguito dalla sequenza di archi sulla seconda riga nel formato seguente:

$$ e_1 \ e_2 \ \ldots \ e_{N-1} $$

Qui, $e_k$ ($1 \le e_k \le N - 1$) rappresenta l'indice dell'arco selezionato nella $k$-esima operazione. Se esistono più sequenze valide, puoi stamparne una qualsiasi.

Esempi

Input 1

3
5
1 2
2 3
2 4
2 5
1 1 1 0 0
2
1 2
0 0
9
1 2
2 3
2 4
4 5
4 6
6 7
6 8
6 9
0 0 1 0 1 1 0 1 1

Output 1

Yes
3 2 4 1
No
Yes
6 7 4 2 1 3 5 8