Universal Cup Judging System

Universal Cup

Límite de tiempo: 4.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.