P9829 [ICPC 2020 Shanghai R] Traveling Merchant

劳伦斯先生是一位在不同城市转售商品的旅行商人。基本地，为了赚钱，他需要以低价买进商品，再以高价卖出。现在请你为他规划一条可以一直盈利的旅行路线。 简单地说，假设有 $n$ 座城市，标号为 $0$ 到 $n-1$ ，以及 $m$ 条连接特定两座城市的路，劳伦斯先生可以通过这些路到访每座城市。最初劳伦斯先生位于第 $0$ 座城市，并且对于城市 $i$ 都有一个起始价格 $c_i$ 。根据市场规律，当他从城市 $i$ 来到相邻的城市 $j$ 时（当且仅当城市 $i$ 与城市 $j$ 之间有路径相连时，才称 $i$ 与 $j$ 为相邻城市），城市 $i$ 的价格状况会发生变化（高价会变成低价，低价也可能变成高价）。而因为一些原因（比如商品的新鲜程度，旅行费用，税务等），他**必须**： - 从城市 $0$ 出发并在城市 $0$ 购买一些商品。保证城市 $0$ 的起始价格很**低**。 - 每当他到达一座城市后，他**必须**售卖**或**购买一些商品。 - 若他在城市 $i$ 购买了商品，他就必须去一座与 $i$ 相邻且价格 $c_j$ **高于** $c_i$ 的城市 $j$ ，并在那里卖掉手中来自城市 $i$ 的商品。 - 若他在城市 $i$ 售卖了商品，他就必须去一座与 $i$ 相邻且价格 $c_j$ **低于** $c_i$ 的城市 $j$，并在那里购买一些商品。 因此，最终路径会始终重复 ``低价购入`` 和 ``高价卖出`` 。 一条无尽的盈利路线由无尽的城市序列 $p_0,p_1 \dots$ 组成。其中，城市 $p_i$ 与城市 $p_{p+1}$ 之间有路径相连，$p_0 = 0$，且价格高低是交替循环的，也就是说当 $k \ge 0$ 时，城市 $p_{2k}$ 的价格 $c_{p_{2k}} = \text{Low}$ (要在这个城市购买商品) 而相邻城市 $p_{2k+1}$ 的价格 $c_{p_{2k+1}} = \text{Hign}$ (要在这个城市卖出商品)。 **注意**：$c_{p_i}$ 是 **到达** 城市 $p_i$ 时的价格，而当他第二次到达城市 $p_i$ 时，这个价格可能会因为市场规律而变化。 你需要写一个程序，判断是否有这样一条永远盈利的路径存在。

无

无

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.