Hoof-Scissors-Rock 1.0: Guaranteed Victory

In this problem, Bessie and Elsie are playing a variant of the classic game with N different hoof gestures (numbered from 1 to \(N\)) corresponding to different materials. The outcome between any two gestures is given by a complex table that determines whether one gesture wins over the other or results in a tie. In a game of Hoof-Scissors-Rock 1.0, each cow shows two gestures (one per hoof). After revealing all four gestures, each player picks one of her two gestures to actually compete, and the result between the chosen gestures is determined by the usual rules.

Bessie has learned Elsie’s plan: Elsie will use a predetermined sequence of M gesture combinations (each combination is an ordered pair of gestures). Bessie now wonders: How many ordered pairs \((L,R)\) (where \(L\) denotes the gesture used on the left hoof and \(R\) on the right hoof) can guarantee her victory regardless of Elsie’s choices?

A Bessie combination \((L,R)\) is said to guarantee victory against an Elsie combination \((E_1,E_2)\) if either gesture L wins against both \(E_1\) and \(E_2\) or gesture R wins against both \(E_1\) and \(E_2\). In other words, if we denote by \(win(a,b)\) the event that gesture \(a\) wins over gesture \(b\) (with a win represented by 1 in the table), then for every Elsie round (with gestures \(E_1,E_2\)), it must hold that

\[ \big( win(L,E_1) = 1 \text{ and } win(L,E_2) = 1 \big) \quad \text{or} \quad \big( win(R,E_1) = 1 \text{ and } win(R,E_2) = 1 \big). \]

You are given the outcome table as well as Elsie’s planned M combinations. Compute the number of Bessie pairs \((L,R)\) (1 \(\le\) L, R \(\le\) N) which guarantee a victory in every game.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \le N \le 3000\), \(1 \le M \le 3000\)).

The following \(N\) lines each contain \(N\) space‐separated integers. The \(j\)th integer in the \(i\)th line represents the outcome when gesture \(i\) is played against gesture \(j\):

• 1 if gesture \(i\) wins against gesture \(j\),
• -1 if gesture \(i\) loses to gesture \(j\),
• 0 if the result is a tie.

The next \(M\) lines each contain two integers \(E_1\) and \(E_2\) representing Elsie’s pair of gestures in that round.

outputFormat

Output a single integer: the number of ordered pairs \((L,R)\) (with \(1 \le L,R \le N\)) for which Bessie can guarantee a victory in every round against Elsie’s planned combinations.

sample

2 2
0 1
1 0
1 1
2 2

2