Combien de personnes peuvent avoir autant de succès que wcysai ?
L'entreprise R est une véritable machine à billets fondée par wcysai, avec un chiffre d'affaires annuel de plus de 100 millions. Il y a $n$ employés qui travaillent dans l'entreprise R, et chaque employé vit dans une maison. Les maisons de certains employés sont reliées par des routes bidirectionnelles. Il est garanti qu'en partant de la maison de n'importe quel employé, on peut rejoindre la maison de n'importe quel autre employé par les routes.
Les employés sont divisés en deux catégories : les managers (type A) et les ouvriers (type B). Un manager travaille $a$ heures par jour, tandis qu'un ouvrier travaille $b$ heures par jour. Évidemment, les ouvriers doivent travailler plus longtemps que les managers, donc $a < b$. Chaque employé a une heure de début de travail $s_i$. Si cet employé doit travailler $m$ heures ($m = a$ ou $m = b$), alors son heure de fin est $t_i = s_i + m$.
Cependant, les employés ne veulent jamais être les plus surmenés. Par conséquent, lorsqu'ils commencent à travailler, ils vérifient si l'un de leurs voisins (c'est-à-dire les employés dont les maisons sont directement reliées par une route) a déjà commencé à travailler. De même, lorsqu'ils terminent leur travail, ils vérifient si l'un de leurs voisins n'a pas encore fini de travailler. Si ces deux observations sont positives, ils se sentent satisfaits. Formellement, un employé est satisfait si et seulement s'il existe un voisin dont l'heure de début est strictement antérieure à la sienne, et s'il existe un voisin dont l'heure de fin est strictement postérieure à la sienne (ces deux voisins peuvent être la même personne ou des personnes différentes). Sinon, l'employé sera insatisfait car il aura l'impression d'être le plus surmené.
Maintenant, en tant qu'assistant compétent de wcysai, vous pouvez organiser librement l'heure de début de chaque employé. Vous souhaitez planifier les horaires de tous les employés de manière raisonnable afin que le nombre de personnes insatisfaites soit minimisé. Notez que vous pouvez attribuer aux heures de début n'importe quels nombres réels positifs ou nuls (voir le format de sortie pour plus de détails).
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 10^5$), le nombre de cas de test.
Pour chaque cas de test, la première ligne contient quatre entiers positifs ou nuls $n$, $m$, $a$ et $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), représentant respectivement le nombre d'employés, le nombre de routes, le nombre d'heures de travail des managers et le nombre d'heures de travail des ouvriers.
La ligne suivante contient une chaîne de caractères de longueur $n$ composée uniquement de A et de B. Le $i$-ème caractère représente le type du $i$-ème employé.
Les $m$ lignes suivantes contiennent chacune deux entiers positifs ou nuls $u, v$ ($1 \le u, v \le n$), représentant une route.
Il est garanti que si les maisons des employés sont considérées comme des sommets et les routes comme des arêtes, le graphe n'a ni arêtes multiples ni boucles, et est connexe.
Il est garanti que la somme de $n$ et la somme de $m$ sur tous les cas de test ne dépassent pas $5 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez une ligne contenant $n$ entiers positifs ou nuls $s'_i$ ($0 \le s'_i \le 10^{18}$). Plus précisément, soit $s_i$ l'heure à laquelle le $i$-ème employé commence à travailler, alors $s_i = \frac{s'_i}{10^6}$. S'il existe plusieurs plannings optimaux qui minimisent le nombre de personnes insatisfaites, affichez l'un quelconque d'entre eux.
Exemple
Entrée 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
Sortie 1
0 1 1 0 2 2 1 0 3 4 2 3 1 4 4000005 0 3000003 3000004 3000002 3000005 3000006 1 0