Universal Cup Judging System

Universal Cup

时间限制: 4.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

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

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.