Wie viele Menschen können so erfolgreich sein wie wcysai?
Firma R ist eine von wcysai gegründete Gelddruckmaschine mit einem Jahresumsatz von über 100 Millionen. Bei Firma R arbeiten $n$ Mitarbeiter, und jeder Mitarbeiter lebt in einem Haus. Die Häuser einiger Mitarbeiter sind durch bidirektionale Straßen miteinander verbunden. Es ist garantiert, dass man vom Haus jedes Mitarbeiters aus über die Straßen das Haus jedes anderen Mitarbeiters erreichen kann.
Die Mitarbeiter sind in zwei Typen unterteilt: Manager (Typ A) und Arbeiter (Typ B). Ein Manager arbeitet $a$ Stunden pro Tag, während ein Arbeiter $b$ Stunden pro Tag arbeitet. Offensichtlich müssen Arbeiter länger arbeiten als Manager, also gilt $a < b$. Jeder Mitarbeiter hat eine Arbeitsbeginnzeit $s_i$. Wenn dieser Mitarbeiter $m$ Stunden arbeiten muss ($m = a$ oder $m = b$), dann ist seine Arbeitsendzeit $t_i = s_i + m$.
Allerdings möchten die Mitarbeiter niemals diejenigen sein, die am meisten überarbeitet sind. Wenn sie mit der Arbeit beginnen, prüfen sie daher, ob einer ihrer Nachbarn (d. h. Mitarbeiter, deren Häuser direkt durch Straßen verbunden sind) bereits mit der Arbeit begonnen hat. Ebenso prüfen sie bei Arbeitsende, ob einer ihrer Nachbarn die Arbeit noch nicht beendet hat. Sind beide Beobachtungen positiv, sind sie zufrieden. Formal ist ein Mitarbeiter genau dann zufrieden, wenn es einen Nachbarn gibt, dessen Startzeit echt früher als seine eigene liegt, und es einen Nachbarn gibt, dessen Endzeit echt später als seine eigene liegt (diese beiden Nachbarn können dieselbe Person oder verschiedene Personen sein). Andernfalls ist der Mitarbeiter unzufrieden, weil er das Gefühl hat, der am meisten Überarbeitete zu sein.
Als fähiger Assistent von wcysai können Sie nun die Arbeitsbeginnzeit jedes Mitarbeiters frei festlegen. Sie möchten alle Mitarbeiter sinnvoll einplanen, sodass die Anzahl der unzufriedenen Personen minimiert wird. Beachten Sie, dass Sie als Startzeiten beliebige nicht-negative reelle Zahlen zuweisen können (Details finden Sie im Ausgabeformat).
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die Anzahl der Testfälle.
Für jeden Testfall enthält die erste Zeile vier nicht-negative ganze Zahlen $n$, $m$, $a$ und $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), die die Anzahl der Mitarbeiter, die Anzahl der Straßen, die Arbeitsstunden der Manager bzw. die Arbeitsstunden der Arbeiter darstellen.
Die nächste Zeile enthält eine Zeichenkette der Länge $n$, die nur aus A und B besteht. Das $i$-te Zeichen gibt den Typ des $i$-ten Mitarbeiters an.
Die nächsten $m$ Zeilen enthalten jeweils zwei nicht-negative ganze Zahlen $u, v$ ($1 \le u, v \le n$), die eine Straße darstellen.
Es wird garantiert, dass der Graph, wenn man die Häuser der Mitarbeiter als Knoten und die Straßen als Kanten betrachtet, keine Mehrfachkanten oder Selbstschleifen aufweist und zusammenhängend ist.
Es wird garantiert, dass die Summe von $n$ und die Summe von $m$ über alle Testfälle hinweg $5 \cdot 10^5$ nicht überschreiten.
Ausgabe
Geben Sie für jeden Testfall eine Zeile mit $n$ nicht-negativen ganzen Zahlen $s'_i$ ($0 \le s'_i \le 10^{18}$) aus. Genauer gesagt: Bezeichnet $s_i$ die Zeit, zu der der $i$-te Mitarbeiter zu arbeiten beginnt, dann gilt $s_i = \frac{s'_i}{10^6}$. Wenn es mehrere optimale Zeitpläne gibt, die die Anzahl der unzufriedenen Personen minimieren, geben Sie einen beliebigen davon aus.
Beispiel
Eingabe 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
Ausgabe 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0