Universal Cup Judging System

Universal Cup

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

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$) берілген.

Келесі жолда тек 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.