有幾多人可以好似 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