{"problem":{"name":"[ICPC 2020 Shanghai R] Traveling Merchant","description":{"content":"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 tas","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9829"},"statements":[{"statement_type":"Markdown","content":"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.\n\nTo 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}$:\n\n- Start at city $0$ and buy products at city $0$. It is guaranteed that $c_0$ is $\\text{Low}$.\n- 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.\n- 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$.\n- 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$.\n\nAs a result, the path will look like an alternation between ``buy at low price`` and ``sell at high price``.\n\nAn 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.\n\nYour task is to determine whether there exists any such path.\n\n## Input\n\nThere 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. \n\nThe next line is a string $c$ of length $n$ containing `H` or `L`. The $i$-th ($0\\le i<n$) charactor of $c$ is $H$ if the starting price $c_i$ at city $i$ is $\\text{High}$. The $i$-th ($0\\le i<n$) charactor of $c$ is $L$ if the starting price $c_i$ at city $i$ is $\\text{Low}$. \n\nThe $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$.\n\nThe 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<n$ and $u_i\\neq v_i$ hold for each $i\\in \\{1,\\ldots, m\\}$. No two roads connect the same pair of cities.\n\n## Output\n\nFor each test case, output a line of ``yes`` or ``no``, indicating whether there exists an endless earning path.\n\n[samples]\n\n## Note\n\nIn 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.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2ohq2wfi.png)\n\nIn 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.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/fcv1tw87.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9829","tags":["2020","上海","O2优化","双连通分量","最近公共祖先 LCA","ICPC"],"sample_group":[["2\n4 4\nLHLH\n0 1\n1 2\n1 3\n2 3\n3 3\nLHH\n0 1\n0 2\n1 2","yes\nno"]],"created_at":"2026-03-03 11:09:25"}}