Forests

Interview

Time limit1sMemory limit128 MB

Summary

Count how many distinct nonempty sets of trees appear among the (person, tree) pairs; people who heard nothing are excluded.

Level: Easy3 of 10
Topics: Hash map, Sorting, Array, Implementation
Solved: No attempts yet

Problem

If a tree falls in the forest, and there is nobody there to hear it, 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 came to be called subjective idealism. He wrote a number of works, of which the most widely read are A 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.

Input

A forest contains $T$ trees, numbered from $1$ to $T$ , and $P$ people, numbered from $1$ to $P$ .

The first line contains two integers: the number of people $P$ and the number of trees $T$ (both less than $100$ ). Each of the following lines contains a pair of integers $i$ and $j$ , indicating that person $i$ has heard tree $j$ fall.

Different people may hold different opinions about which trees, according to Berkeley, have made a sound.

Output

Print a single integer: the number of different opinions represented in the input. Two people hold the same opinion only if they have heard exactly the same set of trees fall.

A person who is never mentioned in any pair has heard no trees fall and expresses no opinion, so they are not counted. In particular, if the input contains no pairs, print $0$ .

Examples3

Example 1
Input
```
3 4
1 2
3 3
1 3
2 2
3 2
2 4
```
Expected output
```
2
```
Example 2
Input
```
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
2 3
1 1
2 2
```
Expected output
```
2
```