Universal Cup Judging System

Universal Cup

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

Чи багато людей можуть стати такими ж успішними, як 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.