Ceiling Function

Interview

Time limit5sMemory limit512 MB

Summary

Insert each prototype's values into a binary search tree in order, then count how many distinct tree shapes appear across the prototypes.

Level: Medium4 of 10
Topics: Tree, Implementation, Hash map
Solved: No attempts yet

Problem

Advanced Ceiling Manufacturers (ACM) analyzes the properties of its new line of Incredibly Collapse-Proof Ceilings (ICPCs). One ICPC is built from a stack of material layers, and every layer has its own collapse resistance, measured as a positive integer. The analysis ACM plans to run takes the collapse-resistance values of the layers, stores them in a binary search tree, and checks whether the shape of that tree says anything about the quality of the whole ceiling. Because, well, why should it not?

ACM reads the collapse-resistance values in order from the top layer to the bottom layer and inserts them one by one into a tree. The rules for inserting a value $v$ are:

If the tree is empty, make $v$ the root of the tree.
If the tree is not empty, compare $v$ with the root. If $v$ is smaller, insert $v$ into the left subtree of the root, otherwise insert $v$ into the right subtree.

ACM has a set of ceiling prototypes it wants to analyze by trying to collapse them. It groups the prototypes whose trees have the same shape and analyzes each group together.

Take the five prototypes of three layers each from the first example below. The first prototype has collapse-resistance value 2 in its top layer, 7 in the middle layer, and 1 in the bottom layer. The second prototype has layers 3, 1, and 4, yet both prototypes induce the same tree shape, so ACM analyzes them together.

Given a set of prototypes, determine how many different tree shapes they induce.

Tree shapes induced by the first example

The figure above shows the four tree shapes induced by the prototypes in the first example.

Input

The first line contains two integers $n$ ( $1 \le n \le 50$ ), the number of ceiling prototypes to analyze, and $k$ ( $1 \le k \le 20$ ), the number of layers in each prototype.

Each of the next $n$ lines describes one prototype. Such a line contains $k$ distinct integers between $1$ and $1\,000\,000$ , inclusive, which are the collapse-resistance values of the layers ordered from top to bottom.

Output

Print the number of different tree shapes.

Examples3

Example 1
Input
```
5 3
2 7 1
3 1 4
1 5 9
2 6 5
9 7 3
```
Expected output
```
4
```
Example 2
Input
```
3 4
3 1 2 40000
3 4 2 1
33 42 17 23
```
Expected output
```
2
```
Example 3
Input
```
1 1
1
```
Expected output
```
1
```