Problem H
All Friends

Sociologists are interested in the phenomenon of “friendship”. To study this property, they analyze various groups of people. For each two persons in such a group they determine whether they are friends (it is assumed that this relation is symmetric). The sociologists are mostly interested in the sets of friends. A set $S$ of people is a set of friends if every two persons in $S$ are friends. However, studying the sets of friends turns out to be quite complicated, since there are too many such sets. Therefore, they concentrate just on the maximal sets of friends. A set of friends $S$ is maximal if there is no person outside $S$ who is friends with everyone in $S$.

Your task is to determine the number of maximal sets of friends in each group. In case this number exceeds $1\, 000$, you just need to report this – such a group is too complicated to study.


The input consists of several instances, separated by single empty lines.

The first line of each instance consists of two integers $1 \le n \le 128$ and $0 \le m \le {n \choose 2}$ – the number of people in the group and the number of friendship relations. Each of the $m$ following lines consists of two integers $a_ i$ and $b_ i$ ($1 \le a_{i}, b_{i} \le n$). This means that persons $a_{i}$ and $b_{i}$ ($a_{i} \ne b_{i}$) are friends. Each such relationship is described at most once.


The output for each instance consists of a single line containing the number of maximal sets of friends in the described group, or the string “Too many maximal sets of friends.” (including the period!) in case this number is greater than $1\, 000$.

Sample Input 1 Sample Output 1
5 4
1 2
3 4
2 3
4 5

Please log in to submit a solution to this problem

Log in