这场真是酣畅淋漓，让我回想起了第一次切 D 的那场。
2h 后还在过题，真是神了。
难度不会评（
D1
为方便表示，记“非负”为正。
注意到 m=n(n+1)2m=\frac{n(n+1)}{2}m=2n(n+1) ，则每个点都有连向自己的一条边。我们又知道 x+xx+xx+x 的正负性与 xxx 相同，所以这其实就是告诉我们每个点的点权符号，让你判断这个合不合法。
我们看到其它边。以 Ax+Ay≥0A_x+A_y\ge 0Ax +Ay ≥0 的边为例，Ax+Ay<0A_x+A_y\lt 0Ax +Ay <0 的边同理。
考虑建个新图，表示 ∣Ai∣|A_i|∣Ai ∣ 的大小关系。
* 若 Ax≥0,Ay≥0A_x\ge 0,A_y\ge 0Ax ≥0,Ay ≥0，则 Ax+AyA_x+A_yAx +Ay 一定 ≥0\ge 0≥0，这条边没有用。
* 若 Ax<0,Ay<0A_x\lt 0,A_y\lt 0Ax <0,Ay <0，则 Ax+AyA_x+A_yAx +Ay 一定 <0\lt 0<0，与这条边矛盾，不合法。
* 若 Ax≥0,Ay<0A_x\ge 0,A_y\lt 0Ax ≥0,Ay <0，则移个项，Ax≥−AyA_x\ge-A_yAx ≥−Ay ，也就是说，这个约束其实代表 ∣Ax∣≥∣Ay∣|A_x|\ge |A_y|∣Ax ∣≥∣Ay ∣。然后呢？我们将新图中 yyy 连向 xxx。
* Ax<0,Ay≥0A_x\lt 0,A_y\ge 0Ax <0,Ay ≥0 同理。
注意到，新图中的边两点一定满足一正一负一正一负，而且正常来说这是个 DAG。如果出现了环，显然有矛盾。
然后我们随便拓扑排序一下，就可以求出任意解了。
时间复杂度：O(∑n+m)O(\sum n+m)O(∑n+m)。
D2
现在，AiA_iAi 的符号未知了。但是如果你能求出一种可能的 AiA_iAi 符号方案，那么就可以套 D1 了。
显然，对于一条 Ax+Ay≥0A_x+A_y\ge 0Ax +Ay ≥0 的边，一定需要满足 Ax≥0A_x\ge 0Ax ≥0 或 Ay≥0A_y\ge 0Ay ≥0；对于一条 Ax+Ay<0A_x+A_y\lt 0Ax +Ay <0 的边，一定需要满足 Ax<0A_x\lt 0Ax <0 或 Ay<0A_y\lt 0Ay <0。
所以，我们可以考虑通过这个跑一个 2-SAT。
但这么做为什么是对的？不会有些 2-SAT 有解，但原问题无解吗？
我们看回 D1 是如何判断不合法的。
* Ax,AyA_x,A_yAx ,Ay 同号但与连向 x,yx,yx,y 的边异号：你都跑 2-SAT 了，这种情况还能发生？
* 建的新图有环：这个是有可能 2-SAT 有解的，但是思考一下，这种情况一定是原来的边满足形如 (1,S1,S2),(2,S2,S3),(1,S3,S4),...,(1,S2k−1,S2k),(2,S2k,S1)(1,S_1,S_2),(2,S_2,S_3),(1,S_3,S_4),...,(1,S_{2k-1},S_{2k}),(2,S_{2k},S_1)(1,S1 ,S2 ),(2,S2 ,S3 ),(1,S3 ,S4 ),...,(1,S2k−1 ,S2k ),(2,S2k ,S1 )，这种情况下无论如何构造都不可能满足的，所以大胆输出 NO 即可。
所以跑 2-SAT 即可。
fun fact：我场上不会 2-SAT，现场学的。所以这题是我切的第一道 2-SAT 题。
时间复杂度：O(∑n+m)O(\sum n+m)O(∑n+m)。
