题目描述

lbw 正在玩流行的游戏 Hunt。在这个游戏中，有 $N$个格子排成一行，编号从 $1$ 到 $N$。每个格子上的字符是 $M$ 或 $O$，第 $i$ 个格子上的字符为 $s_i$。

lbw 计划进行 $K$次移动。在她的第 $i$ 次移动中，lbw 会点击 $3$ 个不同的格子 $(x_{i}, y_{i}, z_{i})$。如果 $s_{x_i}=M$ 且 $s_{y_i}=s_{z_i}=O$，lbw 将获得一分。换句话说，如果她按照顺序点击格子 $x_{i}, y_{i}, z_{i}$ 形成的字符串是 $MOO$，她就会得分。

有人想要帮助 lbw 获得一个新的高分。他希望你在所有可能的棋盘配置中，找出 lbw 进行这 $K$ 次移动所能获得的最大可能得分，以及能使 lbw 达到这个最大可能得分的不同棋盘的数量。两个棋盘被认为是不同的，当且仅当存在一个格子，其上的字符不同。

输入格式

第一行包含 $N$ 和 $K$，表示格子的数量和 lbw 将进行的移动次数。

接下来的 $K$ 行，每行包含 $x_i, y_i, z_i$，描述 lbw 的第 $i$ 次移动（$x_i, y_i, z_i$ 两两不同）。

输出格式

输出 lbw 所能获得的最大可能得分，以及能使 lbw 达到这个最大得分的不同棋盘的数量。

输入样例 #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

说明提示

样例 1 解释

棋盘 $MOOOM$ 和 $MOOMM$ 可以使 lbw 获得最大得分 $4$。在这两个棋盘上，lbw 将在第 $1, 2, 5, 6$ 次移动中得分。可以证明这是 lbw 能够获得的最大得分，并且只有这两个棋盘能使 lbw 获得 $4$ 分。

样例 2 解释

能使 lbw 获得最大可能得分 $6$ 的棋盘是 $OOMOOO$、$OOMMOO$ 和 $OOMOOM$。

输入样例 #3

3 1
1 3 2

输出样例 #3

1 1

数据范围

$3 \le N \le 20$

$1 \le K \le 2 \cdot 10^5$

$1 \le x_{i}, y_{i}, z_{i} \le N$

评分

前三个点满足 $N \le 8, K \le 10^4$。

后七个点满足 $N \in \{14,15,16,17,18,19,20\}$，且对 $K$ 没有额外限制。