有多少人能像 wcysai 一樣成功?
R 公司是由 wcysai 創立的一家印鈔公司,年營收超過 1 億。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