RoAlgo Contest #5 - Back to School Edition | ABgraf

You are given an undirected graph with $n$ nodes and $m$ edges, where each node is of type A or B. Since connected graphs are more visually pleasing than other graphs, our goal is to determine if at least one of the two subgraphs, formed by nodes and edges connecting nodes of type A or B, can become connected by strategically changing the type of at most one node.

Task

For each of the $t$ given graphs, determine if at least one of the two subgraphs can become connected by conveniently changing the type of at most one node.

Input data

The first line contains $t$, the number of tests. Then, the structure of each test follows.

For each test, we first have two values, $n$ and $m$, representing the number of nodes and the number of edges in the initial graph.

The next line contains a string of length $n$, where $s_i$ represents the type of node $i$ (A or B).

The following $m$ lines contain the edges of the graph, with each pair $(a, b)$ representing an edge from $a$ to $b$.

Output data

For each test, output DA (YES) or NU (NO) depending on the answer to the given question.

Constraints and clarifications

• $1 \leq t \leq 100 \ 000$;
• $2 \leq n, m \leq 200 \ 000$;
• $1 \leq \sum{n}, \sum{m} \leq 600 \ 000$;
• Ignoring the letters of each node, the initial graph is always connected.
• The graph can have multiple edges between the same two nodes.

Example

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

Explanation

For the first test, by changing any node, we can make at least one of the two subgraphs connected.

For the fourth test, it is impossible to obtain a connected subgraph.