Universal Cup Judging System

Universal Cup

時間限制: 4.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Ilu ludzi może odnieść taki sukces jak wcysai?

Firma R to maszynka do robienia pieniędzy założona przez wcysai, o rocznych przychodach przekraczających 100 milionów. W Firmie R pracuje $n$ pracowników, a każdy z nich mieszka w swoim domu. Domy niektórych pracowników są połączone dwukierunkowymi drogami. Gwarantuje się, że wyruszając z domu dowolnego pracownika, można dotrzeć drogami do domu każdego innego pracownika.

Pracownicy dzielą się na dwa typy: menedżerów (typ A) i robotników (typ B). Menedżer pracuje $a$ godzin dziennie, natomiast robotnik pracuje $b$ godzin dziennie. Oczywiście robotnicy muszą pracować dłużej niż menedżerowie, więc $a < b$. Każdy pracownik ma czas rozpoczęcia pracy $s_i$. Jeśli ten pracownik musi przepracować $m$ godzin ($m = a$ lub $m = b$), to czas zakończenia jego pracy wynosi $t_i = s_i + m$.

Pracownicy nigdy jednak nie chcą być tymi najbardziej przepracowanymi. Dlatego rozpoczynając pracę, sprawdzają, czy którykolwiek z ich sąsiadów (czyli pracowników, których domy są bezpośrednio połączone drogami) już zaczął pracę. Podobnie kończąc pracę, sprawdzają, czy którykolwiek z ich sąsiadów jeszcze jej nie skończył. Jeśli obie obserwacje są pozytywne, czują się usatysfakcjonowani. Formalnie pracownik jest usatysfakcjonowany wtedy i tylko wtedy, gdy istnieje sąsiad, którego czas rozpoczęcia pracy jest ostro wcześniejszy niż jego własny, oraz istnieje sąsiad, którego czas zakończenia pracy jest ostro późniejszy niż jego własny (ci dwaj sąsiedzi mogą być tą samą osobą lub różnymi osobami). W przeciwnym razie pracownik będzie niezadowolony, ponieważ poczuje, że jest najbardziej przepracowany.

Teraz, jako zdolny asystent wcysai, możesz dowolnie ustalić czas rozpoczęcia pracy każdego pracownika. Chcesz zaplanować pracę wszystkich pracowników w rozsądny sposób, tak aby zminimalizować liczbę niezadowolonych osób. Zauważ, że jako czasy rozpoczęcia możesz przypisać dowolne nieujemne liczby rzeczywiste (szczegóły w formacie wyjścia).

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera cztery nieujemne liczby całkowite $n$, $m$, $a$ oraz $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), oznaczające odpowiednio liczbę pracowników, liczbę dróg, liczbę godzin pracy menedżerów oraz liczbę godzin pracy robotników.

Następny wiersz zawiera napis o długości $n$ składający się wyłącznie ze znaków A oraz B. $i$-ty znak oznacza typ $i$-tego pracownika.

Kolejne $m$ wierszy zawiera po dwie nieujemne liczby całkowite $u, v$ ($1 \le u, v \le n$), oznaczające drogę.

Gwarantuje się, że jeśli potraktujemy domy pracowników jako wierzchołki, a drogi jako krawędzie, to graf nie ma krawędzi wielokrotnych ani pętli własnych i jest spójny.

Gwarantuje się, że suma $n$ oraz suma $m$ we wszystkich przypadkach testowych nie przekraczają $5 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ nieujemnych liczb całkowitych $s'_i$ ($0 \le s'_i \le 10^{18}$). Dokładniej, niech $s_i$ oznacza czas, w którym $i$-ty pracownik rozpoczyna pracę — wówczas $s_i = \frac{s'_i}{10^6}$. Jeśli istnieje wiele optymalnych harmonogramów minimalizujących liczbę niezadowolonych osób, wypisz dowolny z nich.

Przykład

Wejście 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

Wyjście 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.