Hide

Problem D
Forests

/problems/forests/file/statement/en/img-0001.jpg

If a tree falls in the forest, and there’s nobody there to hear, does it make a sound? This classic conundrum was coined by George Berkeley (1685-1753), the Bishop and influential Irish philosopher whose primary philosophical achievement is the advancement of what has come to be called subjective idealism. He wrote a number of works, of which the most widely-read are Treatise Concerning the Principles of Human Knowledge (1710) and Three Dialogues between Hylas and Philonous (1713) (Philonous, the “lover of the mind,” representing Berkeley himself).

A forest contains $T$ trees numbered from $1$ to $T$ and $P$ people numbered from $1$ to $P$. People may have different opinions as to which trees, according to Berkeley, have made a sound. Given who has heard which trees fall, how many different opinions are there? Two people hold the same opinion only if they hear exactly the same set of trees.

Input

Standard input consists of a line containing $1 \le P < 100$ and $1 \le T < 100$ followed by at most $T \cdot P$ lines (terminated by end-of-file), each containing a pair of integers $i$ and $j$, indicating that person $i$ has heard tree $j$ fall. No pair $i$ and $j$ appears more than once.

Output

Output the number of different opinions represented in the input.

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

Please log in to submit a solution to this problem

Log in