P9829 [ICPC 2020 Shanghai R] Traveling Merchant

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 $\textbf{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\geq0$. Please note here $c_{p_i}$ is the price when $\textbf{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 $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

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

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.