和人一样，牛也喜欢站得离朋友较近的位置。 F J FJ FJ有 N ( 2 < = N < = 1 , 000 ) N(2<=N<=1,000) N(2<=N<=1,000)头牛，编号为 1.. N 1..N 1..N,现在要设计一个顺序让他们站成一排给他们喂食。奶牛们按照编号顺序依次站立，允许有多只牛站在同一位置（也就是说，牛i和牛j(i<j)的站立位置 s i , s j s_i,s_j si,sj一定满足 s i < = s j , s_i<=s_j, si<=sj,如果 s i = s j s_i=s_j si=sj,那么编号为i到j之间的牛也一定站在 s i s_i si处）。 有一些牛相互喜欢，希望两人的距离在某个范围内，同样也有一些牛相互不喜欢，希望两人的距离大于等于某个距离，题目中给出 M L ( 1 < = M L < = 10 , 000 ) ML(1<=ML<=10,000) ML(1<=ML<=10,000)个限制描述相互喜欢的情况，给出 M D ( 1 < = M D < = 10 , 000 ) MD(1<=MD<=10,000) MD(1<=MD<=10,000)个限制描述相互不喜欢的情况。 你的任务是计算，如果存在某种方案满足上述要求，输出1号牛和N号牛之间最大距离。
差分约束
对于此题，状态只有朋友与敌人两种。那么，就有 u − v ≤ c u-v \le c u−v≤c 或者 u − v ≥ c u - v \ge c u−v≥c
对于 u − v ≤ c u-v \le c u−v≤c，可以用求最短路中的 d i s [ v ] = d i s [ u ] + e [ i ] . d i s dis[v] = dis[u] + e[i].dis dis[v]=dis[u]+e[i].dis 我们对 u − v ≥ c u - v \ge c u−v≥c 转换成 v − u ≤ − c v-u \le -c v−u≤−c
这样，我们就可以 S P F A SPFA SPFA
求解过程中会有三种情况：
1.如果没有合法方案，输出 -1。判断是否存在负环
2.如果有合法方案，但 1 号奶牛可以与 N 号奶牛相距无穷远，输出 -2.
3.否则，输出 1 号奶牛与 N 号奶牛间的最大距离
