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.m undirected roads each of which connecting two cities. Mr. Lawrence can travel between cities along the roads. Initially he is located at city. High. Due to the law of markets, the price status at city. Low price, or vice versa) after he departs for a neighboring city. 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.As a result, the path will look like an alternation between buy at low priceand sell at high price.An endless earning path is defined as a path consisting of an endless sequence of cities. and this value may be different when he arrives the second time.Your task is to determine whether there exists any such path.
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} n cities named from {0} 0 to {n-1} n−1 and {m} 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} 0 and each of the city {i} i has a starting price c_i c i , either text{Low} Low or text{High} High. Due to the law of markets, the price status at city {i} i will change (i.e. text{High} High price will become text{Low} Low price, or vice versa) after he departs for a neighboring city {j} j from {i} i. (City {j} j is a neighboring city of city {i} i when one of the {m} m roads connects city {i} i and city {j} j.) For some reasons (e.g. product freshness, traveling fee, tax), he must: Start at city {0} 0 and buy products at city {0} 0. It is guaranteed that c_0 c is text{Low} 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} i, he must travel to some neighboring city {j} j whose price c_j c j is text{High} High and sell the products at city {j} j. After selling products at some city {i} i, he must travel to some neighboring city {j} j whose price c_j c j is text{Low} Low and buy the products at city {j} 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 p ,p 1 ,… where city p_i p i and city p_{i+1} p i+1 has a road, p_0=0 p =0, and the price alternates, in other words c_{p_{2k}}=text{Low} c p 2k =Low (indicates a buy-in) and c_{p_{2k+1}}=text{High} c p 2k+1 =High (indicates a sell-out) for k geq 0 k≥0. Please note here c_{p_i} c p i is the price when arriving city p_i 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.
