Moo Hunt

Bessie chơi một trò chơi trên bảng gồm $N$ ô, mỗi ô chứa ký tự 'M' hoặc 'O'. Cô ấy thực hiện $K$ lượt chơi, mỗi lượt chọn ba ô khác nhau $x_i,y_i,z_i$.

Bessie ghi được một điểm trong lượt thứ $i$ nếu ô $x_i$ chứa 'M' và cả hai ô $y_i$, $z_i$ đều chứa 'O' (tức là ba ô tạo thành mẫu "MOO" theo thứ tự).

Hãy tìm cách gán ký tự cho $N$ ô sao cho tổng điểm đạt được là lớn nhất. Đồng thời, đếm số cách gán khác nhau đạt được điểm tối đa đó.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ ($3\le N\le 20$) và $K$ ($1\le K\le 2\times {10}^5$).
• $K$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i,y_i,z_i$ (đôi một khác nhau, $1\le x_i,y_i,z_i\le N$).

Dữ liệu ra

In ra hai số nguyên: điểm tối đa có thể đạt được và số cách gán bảng đạt được điểm tối đa đó.

Ràng buộc

• $3\le N\le 20$
• $1\le K\le 2\times {10}^5$
• Trong mỗi lượt, ba ô $x_i,y_i,z_i$ đôi một khác nhau. Hai lượt khác nhau có thể trùng nhau hoàn toàn, khi đó mỗi lượt vẫn được tính điểm riêng.

Ví dụ