Binary Search Tree Shape Analysis for ICPC Ceilings

Advanced Ceiling Manufacturers (ACM) is analyzing their new series of Incredibly Collapse-Proof Ceilings (ICPCs) by examining the shape of a binary search tree constructed from the collapse-resistance values of each ceiling's layers.

The tree is built by inserting the values one-by-one following these rules:

• If the tree is empty, the value \(v\) becomes the root.
• If the tree is not empty, compare \(v\) with the current node. If \(v < \text{node value}\), insert \(v\) into the left subtree; otherwise, insert it into the right subtree.

Two trees are considered to have the same shape if their structures are identical regardless of the specific values stored in the nodes.

Your task is to count how many distinct tree shapes are produced by a set of ceiling prototypes.

inputFormat

The first line contains two integers (n) and (k), where (n) is the number of ceiling prototypes and (k) is the number of layers in each prototype. Each of the following (n) lines contains (k) positive integers representing the collapse-resistance values from the top layer to the bottom layer.

outputFormat

Output a single integer that is the number of distinct binary search tree shapes generated from the prototypes.

sample

5 3
2 7 1
3 1 4
1 5 9
2 6 5
3 5 8

4