Universal Cup Judging System

Universal Cup

実行時間制限: 4.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

有幾多人可以好似 wcysai 咁成功呢?

R 公司係一間由 wcysai 創立嘅印銀紙公司,年營收超過 1 億。有 $n$ 名員工喺 R 公司返工,每名員工都住喺一間屋入面。部分員工嘅屋之間有雙向道路連接。保證由任何一名員工嘅屋出發,都可以透過道路去到其他任何一名員工嘅屋。

員工分為兩類:經理(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.