Problem 2. Moo Hunt

USACO 2026 Second Contest, Bronze

Bessie is playing the popular game "Moo Hunt". In this game, there are $N$ ($3 \le N \le 20$) cells in a line, numbered from $1$ to $N$. All cells either have the character $M$ or $O$ with the $i$-th cell having character $s_i$.

Bessie plans to perform $K$ ($1 \le K \le 2 \cdot 10^5$) mooves. On her $i$-th moove, Bessie will tap $3$

different

cells ($x_{i},y_{i},z_{i}$) ($1 \le x_{i},y_{i},z_{i} \le N$). Bessie will earn a point if $s_{x_i}=M$ and $s_{y_i}=s_{z_i}=O$. In other words, Bessie will earn a point if she forms the string $MOO$ by tapping cells $x_{i},y_{i},z_{i}$ 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 $K$ 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.

INPUT FORMAT (input arrives from the terminal / stdin):

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

Each of the next $K$ lines contains $x_i, y_i, z_i$ describing Bessie's $i$-th move ($x_i, y_i, z_i$ are pairwise distinct).

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4 2

The boards $MOOOM$ and $MOOMM$ allow Bessie to achieve a maximum score of $4$. In both boards, Bessie will earn points on mooves $1,2,5,6$. 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 $4$.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

6 3

The boards that allow Bessie to achieve a maximum possible score of $6$ are $OOMOOO$, $OOMMOO$, and $OOMOOM$.

SCORING: Inputs 3-5: $N \le 8, K \le 10^4$Inputs 6-12: There will be one test for each $N \in \{14,15,16,17,18,19,20\}$ with no additional constraints on $K$.

Problem credits: Alex Liang