Determining Unique Balance Outcomes

You are given n weights, each weighing either \(1\) gram, \(2\) grams, or \(3\) grams. You do not know the exact weight of each weight; however, you are given some pairwise strict inequalities between some weights. In other words, for some pairs \(i, j\) you know that \(w_i < w_j\) (where \(w_i\) denotes the weight of the \(i\)th weight).

You have already placed two specific weights, denoted by indices A and B, on the left pan of a balance. Now, you must choose two distinct weights from the remaining ones to place on the right pan. However, because the actual weights are unknown (only their possible values and some order relations are known), the outcome of the weighing (i.e. whether the left pan is heavier, the pans balance, or the right pan is heavier) may not be uniquely determined.

Your task is to count the number of ways to select two weights to put on the right pan such that the outcome is uniquely determined to be one of the following:

• Left pan heavier (denote the count as \(c_1\));
• Both pans balance (denote the count as \(c_2\));
• Right pan heavier (denote the count as \(c_3\)).

In other words, for a valid selection the following must hold regardless of how the weights are assigned values (subject to the constraints and the fact that each weight must be 1, 2, or 3 grams):

• If \(S_L\) is the sum of the two left-pan weights and \(S_R\) is the sum of the two right-pan weights, then either \(S_L > S_R\), \(S_L = S_R\), or \(S_L < S_R\) is forced by the constraints.

Hint on the approach:

For each weight \(i\) let \(L_i\) and \(R_i\) be, respectively, the minimum and maximum possible weight it can take given the following:

• Initially, \(L_i=1\) and \(R_i=3\).
• For every inequality \(i<j\): update \(L_j = \max(L_j, L_i+1)\) and update \(R_i = \min(R_i, R_j-1)\).

Then the left pan sum lies in the interval \([L_A+L_B,\; R_A+R_B]\), and for any candidate pair (say weights \(i\) and \(j\)) on the right pan the possible sum lies in \([L_i+L_j,\; R_i+R_j]\). A candidate selection is considered uniquely determined if:

• \(c_1\): if \(L_A+L_B > R_i+R_j\) (the left pan is always heavier),
• \(c_3\): if \(R_A+R_B < L_i+L_j\) (the right pan is always heavier),
• \(c_2\): if both sums are fixed (i.e. \(L_A+L_B = R_A+R_B\) and \(L_i+L_j = R_i+R_j\)) and the two are equal.

Only count ways where one of the above conditions is satisfied.

inputFormat

The input consists of:

 n m
 A B
 u1 v1
 u2 v2
 ...
 um vm

where:

• n is the number of weights (indexed from 1 to n).
• m is the number of known inequalities.
• A and B (\(A \neq B\)) are the indices of the two weights placed on the left pan.
• Each of the following m lines contains two integers u and v indicating that \(w_u < w_v\) (i.e. the uth weight is lighter than the vth weight).

outputFormat

Output three space‐separated integers: \(c_1\) (the number of selections that guarantee the left pan is heavier), \(c_2\) (the number of selections that guarantee balance), and \(c_3\) (the number of selections that guarantee the right pan is heavier).

sample

6 4
5 6
1 3
2 4
3 5
4 6

6 0 0

</p>