Minimum Adjacent Swaps for Restaurant Ordering

In this problem, you are given ( n ) restaurants numbered from 1 to ( n ) and ( m ) preference constraints. Each constraint is a pair of integers ( (a, b) ) which indicates that restaurant ( a ) must appear before restaurant ( b ) in the final ordering. Initially, the restaurants are arranged in increasing order: 1, 2, ( \ldots ), ( n ). You are allowed to swap only adjacent restaurants. Your task is to determine the minimum number of adjacent swaps required to obtain an ordering that satisfies all the given preferences. If it is impossible to satisfy all the preferences (i.e. the constraints are contradictory and form a cycle), output -1.

Note: The minimum number of adjacent swaps required to transform one permutation into another is equivalent to the Kendall tau distance, which can be computed by counting the number of inversions: [ \text{swaps} = \sum_{i<j} [p_i > p_j], ] where ( [p_i > p_j] ) is 1 if ( p_i > p_j ) and 0 otherwise.

Examples:

• Input: n = 4, m = 2, preferences = [(1, 2), (3, 4)] — The initial order [1,2,3,4] already satisfies the constraints, so the answer is 0.
• Input: n = 4, m = 3, preferences = [(1, 2), (2, 3), (3, 4)] — The initial order is valid; output 0.
• Input: n = 4, m = 4, preferences = [(1, 2), (2, 3), (3, 4), (4, 1)] — The constraints form a cycle; output -1.
• Input: n = 4, m = 3, preferences = [(1, 3), (2, 1), (4, 3)] — A valid ordering is [2, 1, 4, 3] which can be obtained from [1,2,3,4] in 2 adjacent swaps; output 2.

inputFormat

The input is read from standard input (stdin). The first line contains two integers ( n ) and ( m ) separated by a space, denoting the number of restaurants and the number of preference constraints, respectively. The following ( m ) lines each contain two integers ( a ) and ( b ) (separated by a space), representing a constraint that restaurant ( a ) must appear before restaurant ( b ) in the final ordering.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of adjacent swaps required to rearrange the restaurants to satisfy all the preferences, or -1 if it is impossible.## sample

4 2
1 2
3 4

0