Quante persone possono avere lo stesso successo di wcysai?
L'Azienda R è una macchina da soldi fondata da wcysai, con un fatturato annuo di oltre 100 milioni. Ci sono $n$ dipendenti che lavorano presso l'Azienda R, e ogni dipendente vive in una casa. Le case di alcuni dipendenti sono collegate da strade bidirezionali. È garantito che, partendo dalla casa di qualsiasi dipendente, si possa raggiungere la casa di qualsiasi altro dipendente attraverso le strade.
I dipendenti sono divisi in due categorie: manager (tipo A) e operai (tipo B). Un manager lavora $a$ ore al giorno, mentre un operaio lavora $b$ ore al giorno. Ovviamente, gli operai devono lavorare più a lungo dei manager, quindi $a < b$. Ogni dipendente ha un orario di inizio lavoro $s_i$. Se questo dipendente deve lavorare $m$ ore ($m = a$ oppure $m = b$), allora il suo orario di fine lavoro è $t_i = s_i + m$.
Tuttavia, i dipendenti non vogliono mai essere i più sovraccarichi di lavoro. Pertanto, quando iniziano a lavorare, controllano se qualcuno dei loro vicini (ossia i dipendenti le cui case sono direttamente collegate da strade) ha già iniziato a lavorare. Allo stesso modo, quando finiscono di lavorare, controllano se qualcuno dei loro vicini non ha ancora finito di lavorare. Se entrambe le osservazioni sono positive, si sentiranno soddisfatti. Formalmente, un dipendente è soddisfatto se e solo se esiste un vicino il cui orario di inizio è strettamente precedente al suo, ed esiste un vicino il cui orario di fine è strettamente successivo al suo (questi due vicini possono essere la stessa persona o persone diverse). Altrimenti, il dipendente sarà insoddisfatto perché sentirà di essere il più sovraccarico di lavoro.
Ora, in qualità di abile assistente di wcysai, puoi organizzare liberamente l'orario di inizio di ciascun dipendente. Vuoi pianificare gli orari di tutti i dipendenti in modo ragionevole affinché il numero di persone insoddisfatte sia ridotto al minimo. Nota che puoi assegnare come orari di inizio qualsiasi numero reale non negativo (vedi il formato di output per i dettagli).
Input
La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), il numero di casi di test.
Per ogni caso di test, la prima riga contiene quattro interi non negativi $n$, $m$, $a$ e $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), che rappresentano rispettivamente il numero di dipendenti, il numero di strade, le ore di lavoro dei manager e le ore di lavoro degli operai.
La riga successiva contiene una stringa di lunghezza $n$ composta solo da A e B. L'$i$-esimo carattere rappresenta il tipo dell'$i$-esimo dipendente.
Le successive $m$ righe contengono ciascuna due interi non negativi $u, v$ ($1 \le u, v \le n$), che rappresentano una strada.
È garantito che, considerando le case dei dipendenti come vertici e le strade come archi, il grafo non abbia archi multipli o cappi, e sia connesso.
È garantito che la somma di $n$ e la somma di $m$ su tutti i casi di test non superino $5 \cdot 10^5$.
Output
Per ogni caso di test, stampa una riga contenente $n$ interi non negativi $s'_i$ ($0 \le s'_i \le 10^{18}$). Nello specifico, sia $s_i$ l'orario in cui l'$i$-esimo dipendente inizia a lavorare, allora $s_i = \frac{s'_i}{10^6}$. Se esistono più pianificazioni ottimali che minimizzano il numero di persone insoddisfatte, stampane una qualsiasi.
Esempio
Input 1
5 2 1 1 5 AA 1 2 3 3 1 5 ABA 1 2 1 3 2 3 5 4 2 4 BABBB 1 2 1 5 2 3 2 4 6 9 1 5 BABBAB 1 2 1 3 1 4 2 6 3 4 3 5 3 6 4 5 5 6 7 7 2 5 BBAAABB 1 2 1 3 1 5 2 4 3 6 3 7 6 7
Output 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0