Traveling Merchant

题号：NC214903
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

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:

Start at city ${0}$ and buy products at city ${0}$ . It is guaranteed that $c_0$ is $\text{Low}$ .
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.
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}$ .
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,\dots$ 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 \geq 0$ . 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.

输入描述:

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

The next line is a string  of length  containing  or . The -th () charactor of  is  if the starting price  at city  is . The -th () charactor of  is  if the starting price  at city  is . 

The -th line () of the following  lines contains two different cities  and , indicating a road between  and .

The sum of the values of  over all test cases is no more than . The sum of the values of  over all test cases is no more than . For each test case,  holds for each .  is always .  and  hold for each . No two roads connect the same pair of cities.

输出描述:

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

示例1

输入

复制

输出

复制

yes
no

说明

In the first sample test case, the endless earning path is . In the illustration, cities with  price are filled with stripe.


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