Universal Cup Judging System

Universal Cup

Límite de tiempo: 4.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Много ли людей могут стать такими же успешными, как wcysai?

Компания R — это основанная wcysai компания по печатанию денег с годовым доходом более 100 миллионов. В компании R работают $n$ сотрудников, и каждый сотрудник живёт в своём доме. Дома некоторых сотрудников соединены двусторонними дорогами. Гарантируется, что от дома любого сотрудника можно добраться по дорогам до дома любого другого сотрудника.

Сотрудники делятся на два типа: менеджеры (тип A) и рабочие (тип B). Менеджер работает $a$ часов в день, а рабочий — $b$ часов в день. Очевидно, что рабочие должны работать дольше менеджеров, поэтому $a < b$. У каждого сотрудника есть время начала работы $s_i$. Если этому сотруднику нужно проработать $m$ часов ($m = a$ или $m = b$), то время окончания его работы равно $t_i = s_i + m$.

Однако сотрудники ни в коем случае не хотят быть самыми перегруженными работой. Поэтому, начиная работу, они проверяют, начал ли уже работать кто-нибудь из их соседей (то есть сотрудников, чьи дома напрямую соединены дорогами с их домом). Аналогично, заканчивая работу, они проверяют, остался ли кто-нибудь из их соседей, кто ещё не закончил работать. Если оба наблюдения положительны, они чувствуют себя удовлетворёнными. Формально, сотрудник удовлетворён тогда и только тогда, когда существует сосед, чьё время начала работы строго раньше его собственного, и существует сосед, чьё время окончания работы строго позже его собственного (эти два соседа могут быть как одним и тем же человеком, так и разными людьми). В противном случае сотрудник будет недоволен, так как посчитает себя самым перегруженным.

Теперь вы, как способный помощник wcysai, можете свободно назначать время начала работы каждого сотрудника. Вы хотите составить расписание для всех сотрудников так, чтобы минимизировать количество недовольных людей. Обратите внимание, что в качестве времени начала работы можно назначать любые неотрицательные вещественные числа (подробности см. в формате выходных данных).

Входные данные

Первая строка содержит целое число $T$ ($1 \le T \le 10^5$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит четыре неотрицательных целых числа $n$, $m$, $a$ и $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), обозначающих количество сотрудников, количество дорог, продолжительность рабочего дня менеджеров и продолжительность рабочего дня рабочих соответственно.

Следующая строка содержит строку длины $n$, состоящую только из символов A и B. $i$-й символ обозначает тип $i$-го сотрудника.

Следующие $m$ строк содержат по два неотрицательных целых числа $u, v$ ($1 \le u, v \le n$), обозначающих дорогу.

Гарантируется, что если считать дома сотрудников вершинами, а дороги — рёбрами, то граф не содержит кратных рёбер и петель и является связным.

Гарантируется, что сумма $n$ и сумма $m$ по всем наборам входных данных не превышают $5 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $n$ неотрицательных целых чисел $s'_i$ ($0 \le s'_i \le 10^{18}$). А именно, если $s_i$ обозначает время начала работы $i$-го сотрудника, то $s_i = \frac{s'_i}{10^6}$. Если существует несколько оптимальных расписаний, минимизирующих количество недовольных людей, выведите любое из них.

Пример

Входные данные 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

Выходные данные 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.