Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

과연 몇 명이나 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$)가 주어진다.

다음 줄에는 A와 B로만 이루어진 길이 $n$인 문자열이 주어진다. $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.