K. Traveling Merchant
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Lawrence is a traveling merchant who travels between cities and resells products. Basically, to earn from it, he needs to buy products at a very low price and sell them at a higher price. Your task is to tell him whether there exists an endless traveling path that can earn money all the time.

To make things simple, suppose there are $$$n$$$ cities named from $$$0$$$ to $$$n-1$$$ and $$$m$$$ undirected roads each of which connecting two cities. Mr. Lawrence can travel between cities along the roads. Initially he is located at city $$$0$$$ and each of the city $$$i$$$ has a starting price $$$c_i$$$, either $$$\text{Low}$$$ or $$$\text{High}$$$. Due to the law of markets, the price status at city $$$i$$$ will change (i.e. $$$\text{High}$$$ price will become $$$\text{Low}$$$ price, or vice versa) after he departs for a neighboring city $$$j$$$ from $$$i$$$. (City $$$j$$$ is a neighboring city of city $$$i$$$ when one of the $$$m$$$ roads connects city $$$i$$$ and city $$$j$$$.) For some reasons (e.g. product freshness, traveling fee, tax), he must:

  1. Start at city $$$0$$$ and buy products at city $$$0$$$. It is guaranteed that $$$c_0$$$ is $$$\text{Low}$$$.
  2. When he arrives some city, he either sells products or buys products. It is not allowed for him to do nothing before he leaves the city.
  3. After buying products at some city $$$i$$$, he must travel to some neighboring city $$$j$$$ whose price $$$c_j$$$ is $$$\text{High}$$$ and sell the products at city $$$j$$$.
  4. After selling products at some city $$$i$$$, he must travel to some neighboring city $$$j$$$ whose price $$$c_j$$$ is $$$\text{Low}$$$ and buy the products at city $$$j$$$.
As a result, the path will look like an alternation between "buy at low price" and "sell at high price".

An endless earning path is defined as a path consisting of an endless sequence of cities $$$p_0, p_1,...$$$ where city $$$p_i$$$ and city $$$p_{i+1}$$$ has a road, $$$p_0=0$$$, and the price alternates, in other words $$$c_{p_{2k}}=\text{Low}$$$ (indicates a buy-in) and $$$c_{p_{2k+1}}=\text{High}$$$ (indicates a sell-out) for $$$k\geq0$$$. Please note here $$$c_{p_i}$$$ is the price when arriving city $$$p_i$$$ and this value may be different when he arrives the second time.

Your task is to determine whether there exists any such path.

Input

There are several test cases. The first line contains a positive integer $$$T$$$ indicating the number of test cases. Each test case begins with two positive integers $$$n$$$ and $$$m$$$ indicating the number of cities and the number of roads.

The next line is a string $$$c$$$ of length $$$n$$$ containing 'H' or 'L'. The $$$i$$$-th ($$$0\le i \lt n$$$) charactor of $$$c$$$ is $$$H$$$ if the starting price $$$c_i$$$ at city $$$i$$$ is $$$\text{High}$$$. The $$$i$$$-th ($$$0\le i \lt n$$$) charactor of $$$c$$$ is $$$L$$$ if the starting price $$$c_i$$$ at city $$$i$$$ is $$$\text{Low}$$$.

The $$$i$$$-th line ($$$1\le i\le m$$$) of the following $$$m$$$ lines contains two different cities $$$u_i$$$ and $$$v_i$$$, indicating a road between $$$u_i$$$ and $$$v_i$$$.

The sum of the values of $$$n$$$ over all test cases is no more than $$$200,000$$$. The sum of the values of $$$m$$$ over all test cases is no more than $$$200,000$$$. For each test case, $$$c_i\in\{\text{H},\text{L}\}$$$ holds for each $$$i\in \{0, \ldots, n-1\}$$$. $$$c_0$$$ is always $$$L$$$. $$$0\leq u_i,v_i \lt n$$$ and $$$u_i\neq v_i$$$ hold for each $$$i\in \{1,\ldots, m\}$$$. No two roads connect the same pair of cities.

Output

For each test case, output a line of "yes" or "no", indicating whether there exists an endless earning path.

Example
Input
2
4 4
LHLH
0 1
1 2
1 3
2 3
3 3
LHH
0 1
0 2
1 2
Output
yes
no
Note

In the first sample test case, the endless earning path is $$$0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow \dots$$$. In the illustration, cities with $$$\text{Low}$$$ price are filled with stripe.

In the second sample test case, Mr. Lawrence can only make one move from city $$$0$$$ and after that all cities will have $$$\text{High}$$$ price. Thus, no further moves can be made.