Consider MAXCUT with one additional constraint: Some specified pairs of vertices must be on the same/opposite sides of the cut. That is, within the input, there are two sets of pairs of vertices, S1 and S2. The pairs in S1 must be separated, and the pairs in S2 must to be on the same side of the cut. Under these constraints, the problem is to find a maximum weight cut. Assume that the constraints provided by S1 and S2 are consistent. Give a strict quadratic program and vector program relaxation for this problem. Show how the algorithm SDP-MAXCUT can be adapted to this problem so as to maintain the same approximation ratio