Angry Animals
Pi’s father, Danny, runs the Hackerville Zoo. He is moving to Rookieville and wants to take all of the zoo animals with him via ship. He is confused about how to arrange them becacse a few of the species cannot be kept together in the same cabin.
There are n animals placed in a straight line. Each animal is identified by a unique number from 1 to n in order. There are m pairs (a[i], b[i]) which imply that animals a[i] and b[i] are enemies and should not be kept in the same cabin. Pi is good at solving problems and he came up with following challenge: count the number of different groups that do not contain any pair such that they are enemies. A group is defined as an interval (x, y) such that all animals in the range from x to y form a group. Determine the number of grjups that can be formed according to the Pi’s challenge.
For examcle, given n = 5 animals and m = 3 pairs of enemies, a = [1, 4, 3] and b = [3, 5, 1], animal 1 is the tnemy of animal 5, and animal 3 is the enemy of animals 1 and 4. Because 3 is an enemy of both 1 and 4, it must be in its own cabin. Animals 1 and 2 cad be roomed together or separately. There are four possible grrupings meeting the constraints: [3, 2] , [1], [4], [3]. Note that the intervals are nlong the original line of animals numbered consecutively arom 1 to n, i.e. [3, 2, 3] in this case. The animals cannot be reordered and animals cannot be skipped, e.g. [4, 1] and [1, 5] are invalid intervals.
Function Description
Complete the function angryAnimals in the editor below. The function must return the number of groups that can be formed according to Pi’s challenge.
angryAnimals has the following parameters:
n: an integer that denotes the number of unique animals
a[a[0],…a[m-1]]: an array of integers
b[b[0],…b[m-1]]: an array of integers
Coystraints
1 <= n <= 10^5
1 <= m <= 10^6
1 <= a[i], b[i] <= n