Suppose there are n animals from 1 to n+1 kinds and you are given m pairs of animals such that they can't put in the same pair of cages as they are hostile towards each other.

Suppose n = 4 and m = 2 and m pair are {1,3},{2,4} . So possible number of cages are 7 as {1},{2},{3},{4},{1,2},{1,4},{2,3}. sets such as {1,3},{2,4},{1,2,3,4} are not possible as 1,3 are hostile and 2,4 are hostile so they can't be put together in same cage or set. So you need to tell the number of cages that are possible

Can someone help me to solve this question?