Hvor mange mennesker kan bli like suksessrike som wcysai?
Selskap R er et pengetrykkende selskap grunnlagt av wcysai, med en årlig omsetning på over 100 millioner. Det er $n$ ansatte som jobber i Selskap R, og hver ansatt bor i et hus. Noen ansattes hus er forbundet med toveis veier. Det er garantert at man ved å starte fra huset til en hvilken som helst ansatt kan nå huset til enhver annen ansatt gjennom veiene.
De ansatte er delt inn i to typer: ledere (type A) og arbeidere (type B). En leder jobber $a$ timer per dag, mens en arbeider jobber $b$ timer per dag. Åpenbart må arbeidere jobbe lenger enn ledere, så $a < b$. Hver ansatt har et starttidspunkt for arbeidet $s_i$. Hvis denne ansatte må jobbe $m$ timer ($m = a$ eller $m = b$), så er sluttidspunktet deres $t_i = s_i + m$.
Imidlertid ønsker de ansatte aldri å være den som er mest overarbeidet. Derfor, når de begynner på jobb, vil de sjekke om noen av naboene deres (det vil si ansatte hvis hus er direkte forbundet med veier) allerede har begynt å jobbe. På samme måte, når de er ferdige på jobb, vil de sjekke om noen av naboene deres ennå ikke er ferdige med å jobbe. Hvis begge observasjonene er positive, vil de føle seg fornøyde. Formelt er en ansatt fornøyd hvis og bare hvis det finnes en nabo hvis starttidspunkt er strengt tidligere enn deres eget, og det finnes en nabo hvis sluttidspunkt er strengt senere enn deres eget (disse to naboene kan være samme person eller forskjellige personer). Ellers vil den ansatte være misfornøyd fordi de føler at de er den mest overarbeidede.
Nå, som wcysais dyktige assistent, kan du fritt bestemme starttidspunktet for hver ansatt. Du ønsker å planlegge arbeidstiden for alle ansatte på en fornuftig måte slik at antallet misfornøyde personer minimeres. Merk at du kan tilordne starttidspunkter til ethvert ikke-negativt reelt tall (se utdataformatet for detaljer).
Inndata
Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), antallet testtilfeller.
For hvert testtilfelle inneholder den første linjen fire ikke-negative heltall $n$, $m$, $a$ og $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), som representerer henholdsvis antallet ansatte, antallet veier, arbeidstimene til ledere og arbeidstimene til arbeidere.
Den neste linjen inneholder en streng med lengde $n$ som kun består av A og B. Det $i$-te tegnet representerer typen til den $i$-te ansatte.
De neste $m$ linjene inneholder hver to ikke-negative heltall $u, v$ ($1 \le u, v \le n$), som representerer en vei.
Det er garantert at hvis de ansattes hus betraktes som hjørner og veiene som kanter, har grafen ingen parallelle kanter eller løkker, og er sammenhengende.
Det er garantert at summen av $n$ og summen av $m$ over alle testtilfeller ikke overstiger $5 \cdot 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut én linje som inneholder $n$ ikke-negative heltall $s'_i$ ($0 \le s'_i \le 10^{18}$). Spesifikt, la $s_i$ betegne tidspunktet når den $i$-te ansatte begynner å jobbe, da er $s_i = \frac{s'_i}{10^6}$. Hvis det finnes flere optimale tidsplaner som minimerer antallet misfornøyde personer, kan du skrive ut hvilken som helst av dem.
Eksempel
Inndata 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
Utdata 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0