Aprovação de proposta

Os moradores de um condomínio irão votar, dentro de $N$ dias, as $P$ propostas de reforma da fachada dos prédios. Você acabou de elaborar sua proposta e têm apenas $N$ dias para convencer o maior número de pessoas, entre os $M$ moradores, a aderirem à sua ideia.

Assumindo que, em um dia, você convença todos os seus amigos a optarem pela sua proposta (ou, se já tiverem optado pela sua proposta, convencê-los a persuadir os amigos) e que eles consigam fazer o mesmo (isto é, no dia seguinte convençam todos os seus amigos a optarem e/ou trabalharem a favor de sua proposta, e assim por diante), você conseguiria a aprovação de sua proposta?

Cada morador é identificado por um número inteiro de 1 a $M$ (sendo o seu número igual a 1) e cada proposta recebeu uma letra maiúscula distinta como rótulo (a sua proposta tem como rótulo a letra $A$).

Entrada

A primeira linha da entrada contém o número de dias $N$ ($1\leq N\leq 15)$ que antecedem a votação das propostas e o número $M$ ($1\leq M\leq 2\times 10^5)$ de moradores que residem no condomínio, você inclusive.

A segunda linha contém uma string $s$, composta de $M$ letras maiúsculas, onde a $i$-ésima letra ($1\leq i\leq M$) indica a proposta $s_i$ escolhida pelo morador $i$ antes de você iniciar o seu processo de convencimento. É garantido que $s_1 =$ ‘A’.

A linha seguinte contém o valor de $R$ ($0\leq R\leq \min\{M(M - 1)/2, 2\times 10^5\})$, que indica o número de relações de amizade existentes no condomínio. As $R$ linhas seguintes contém, cada uma, um par de inteiros $x$ e $y$ $(1\leq x, y\leq M, x \neq y)$, separados por um espaço em branco, que indicam que o morador $x$ é amigo do morador $y$ (neste caso, $y$ também é amigo de $x$).

Saída

Imprima, em uma linha, a mensagem “Sim”, caso sua proposta seja aprovada, ou a mensagem “Nao”, caso contrário.

Na segunda linha imprima uma string que represente o resultado da eleição, da proposta mais votada para a menos votada, conforme o exemplo. Se duas ou mais propostas tiverem o mesmo número de votos, o desempate será feito pela ordem alfabética dos rótulos das propostas.

Exemplo de entrada 1

2 5
ABBBB
3
2 1
5 4
3 2

Exemplo de saída 1

Sim
AB

Explicação do exemplo 1: ao fim do primeiro dia você convence o morador 2 a aderir à proposta A. No dia seguinte, o morador 2 convence o morador 3. Assim, na eleição a proposta A recebe 3 votos (moradores 1, 2 e 3) e a proposta B apenas 2, de modo que sua proposta obtém a aprovação.

Exemplo de entrada 2

1 5
ABBBB
3
2 1
5 4
3 2

Exemplo de saída 2

Nao
BA

Exemplo de entrada 3

2 10
AABBBBBBBA
8
1 2
2 3
3 4
5 6
6 7
7 8
8 9
9 10

Exemplo de saída 3

Nao
BA

Exemplo de entrada 4

2 10
ABDCFCCCGC
12
10 8
6 10
7 6
10 9
9 8
7 8
6 4
4 5
5 2
2 3
1 2
9 7

Exemplo de saída 4

Nao
CAG