ABgraf

Se dă un graf neorientat cu $n$ noduri și $m$ muchii, fiecare nod fiind de tipul A sau B. Deoarece grafurile conexe sunt mult mai plăcute ochiului decât celelalte grafuri, scopul nostru este să aflăm dacă măcar unul din cele două subgrafuri formate din nodurile și muchiile ce leagă noduri de tipul A sau B poate deveni conex modificând strategic tipul al cel mult unui nod.

Cerință

Pentru fiecare din cele $t$ grafuri date la intrare, spuneți dacă măcar unul din cele două subgrafuri poate deveni conex modificând convenabil tipul cel mult al unui nod.

Date de intrare

Pe prima linie se va găsi $t$, numărul de teste. Apoi, urmează structura fiecărui test.

Pentru fiecare test avem mai întâi două valori, $n$ și $m$, reprezentând numărul de noduri și numărul de muchii ale grafului inițial.

Pe următoarea linie avem un șir de caractere de lungime $n$, $s_i$ fiind tipul nodului $i$ (A sau B).

Pe următoarele $m$ linii avem muchiile grafului, perechea $(a, b)$ reprezentând faptul că avem muchie de la $a$ la $b$.

Date de ieșire

Pentru fiecare test, se va afișa pe o linie DA sau NU în funcție de răspunsul la întrebarea dată.

Restricții și precizări

• $1 \leq t \leq 100 \ 000$;
• $2 \leq n, m \leq 200 \ 000$;
• $1 \leq \sum{n}, \sum{m} \leq 600 \ 000$;
• Dacă facem abstracție de literele fiecărui nod, graful inițial este mereu conex.
• Graful poate avea muchii multiple între aceleași două noduri.

Exemplu

stdin

4
4 3
ABAB
1 2
2 3
3 4
7 9
AAAAABA
1 2
1 4
3 2
5 6
1 3
4 6
5 7
4 2
6 1
8 8
AAABBABB
1 2
2 3
3 4
4 5
4 6
1 6
7 8
4 8
10 12
BAABABABAA
1 6
2 3
3 4
1 7
3 5
4 5
2 4
5 1
2 8
8 9
9 10
10 4

stdout

DA
DA
DA
NU

Explicație

Pentru primul test, orice nod am modifica, am avea măcar unul din cele două subgrafuri conexe.

Pentru cel de-al patrulea test, e imposibil să obținem un subgraf conex.