#215270. [USACO26JAN2] Moo Hunt B

Bessie is playing the popular game "Moo Hunt". In this game, there are () cells in a line, numbered from to . All cells either have the character or with the -th cell having character .

Bessie plans to perform () mooves. On her -th moove, Bessie will tap different cells () (). Bessie will earn a point if and . In other words, Bessie will earn a point if she forms the string by tapping cells in that order.

Farmer John wants to help Bessie get a new high score. He wants you to find the maximum possible score Bessie could get across all possible boards if she performs the mooves as well as the number of different boards that will allow Bessie to achieve this maximum possible score. Two boards are different if there exists a cell such that the corresponding characters at the cell are different.

The first line contains and , the number of cells and the number of mooves Bessie will perform.

Each of the next lines contains describing Bessie's -th move ( are pairwise distinct).

Output the maximum possible score Bessie could achieve, followed by the count of different boards that will allow Bessie to achieve this maximum score.

样例输入 1

5 6
1 2 3
1 2 3
1 3 5
2 3 4
5 3 2
5 2 3

样例输出 1

4 2

样例输入 2

6 12
2 4 3
2 3 4
3 5 2
3 5 1
3 1 5
3 1 2
6 1 5
1 6 4
2 3 6
3 6 2
4 1 6
3 4 2

样例输出 2

6 3

Sample 1 Explanation

The boards and allow Bessie to achieve a maximum score of . In both boards, Bessie will earn points on mooves . It can be shown that this is the maximum score Bessie can achieve, and those two boards are the only possible boards allowing Bessie to achieve a score of .

Sample 2 Explanation

The boards that allow Bessie to achieve a maximum possible score of are , , and .

SCORING:

• Inputs 3-5:
• Inputs 6-12: There will be one test for each with no additional constraints on .