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.

N/A

N/A

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.