Universal Cup Judging System

Universal Cup

시간 제한: 4.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

Hur många människor kan bli lika framgångsrika som wcysai?

Företag R är ett pengatryckande företag grundat av wcysai, med en årlig omsättning på över 100 miljoner. Det finns $n$ anställda som arbetar på Företag R, och varje anställd bor i ett hus. Vissa anställdas hus är förbundna med dubbelriktade vägar. Det garanteras att man med start från vilken anställds hus som helst kan nå vilken annan anställds hus som helst via vägarna.

De anställda är indelade i två typer: chefer (typ A) och arbetare (typ B). En chef arbetar $a$ timmar per dag, medan en arbetare arbetar $b$ timmar per dag. Uppenbarligen måste arbetare arbeta längre än chefer, så $a < b$. Varje anställd har en starttid för arbetet $s_i$. Om denna anställde behöver arbeta $m$ timmar ($m = a$ eller $m = b$), så är deras sluttid $t_i = s_i + m$.

De anställda vill dock aldrig vara den som är mest överarbetad. När de börjar arbeta kontrollerar de därför om någon av deras grannar (det vill säga anställda vars hus är direkt förbundna med vägar) redan har börjat arbeta. På samma sätt kontrollerar de när de slutar arbeta om någon av deras grannar ännu inte har slutat arbeta. Om båda observationerna är positiva känner de sig nöjda. Formellt är en anställd nöjd om och endast om det finns en granne vars starttid är strikt tidigare än deras egen, och det finns en granne vars sluttid är strikt senare än deras egen (dessa två grannar kan vara samma person eller olika personer). Annars kommer den anställde att vara missnöjd eftersom de känner att de är den mest överarbetade.

Nu, som wcysais dugliga assistent, får du fritt bestämma starttiden för varje anställd. Du vill schemalägga alla anställda rimligt så att antalet missnöjda personer minimeras. Observera att du kan tilldela starttider till vilka icke-negativa reella tal som helst (se utdataformatet för detaljer).

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^5$), antalet testfall.

För varje testfall innehåller den första raden fyra icke-negativa heltal $n$, $m$, $a$ och $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), som representerar antalet anställda, antalet vägar, chefernas arbetstimmar respektive arbetarnas arbetstimmar.

Nästa rad innehåller en sträng med längden $n$ som endast består av A och B. Det $i$-te tecknet representerar typen för den $i$-te anställde.

De följande $m$ raderna innehåller var och en två icke-negativa heltal $u, v$ ($1 \le u, v \le n$), som representerar en väg.

Det garanteras att om de anställdas hus betraktas som hörn och vägarna som kanter, så har grafen inga multipelkanter eller öglor, och är sammanhängande.

Det garanteras att summan av $n$ och summan av $m$ över alla testfall inte överstiger $5 \cdot 10^5$.

Utdata

För varje testfall, skriv ut en rad som innehåller $n$ icke-negativa heltal $s'_i$ ($0 \le s'_i \le 10^{18}$). Specifikt, låt $s_i$ beteckna tiden då den $i$-te anställde börjar arbeta, då gäller $s_i = \frac{s'_i}{10^6}$. Om det finns flera optimala scheman som minimerar antalet missnöjda personer, skriv ut vilket som helst av dem.

Exempel

Indata 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

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.