n people at a dance night, numbered 0 to n - 1, with n even. For each person i, the list ranking[i] holds everyone else ordered from most to least liked: the earlier someone appears, the more i likes them.
The organizers have already split everyone into couples: couples[k] = [a, b] means a dances with b.
A person x dancing with y is **envious** if there is a person u dancing with v such that:
- x likes u more than y, and
- u likes x more than v.
Return how many people are envious.n=4, ranking=[[2, 1, 3], [3, 0, 2], [0, 3, 1], [1, 0, 2]], couples=[[0, 1], [2, 3]] → 4
Dancer 0 is paired with 1 but would rather be with 2, and 2 also prefers 0 to their partner 3, so 0 and 2 are envious. Dancer 1 would rather be with 3, and 3 prefers 1 to their partner 2, so both of them are envious too. The answer is 4.
n=4, ranking=[[1, 2, 3], [0, 2, 3], [3, 0, 1], [2, 0, 1]], couples=[[0, 1], [2, 3]] → 0
Everyone is paired with their first choice, so nobody is envious. The answer is 0.
n=2, ranking=[[1], [0]], couples=[[0, 1]] → 0
n ≤ 500, n is evenn, and ranking[i] is a permutation of every number except in / 2n=4, ranking=[[2, 1, 3], [3, 0, 2], [0, 3, 1], [1, 0, 2]], couples=[[0, 1], [2, 3]]
4
Run checks the first 3 tests in your browser. Submit checks all 7 tests on the server, hidden ones included.