G. Longest Increasing Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a simple undirected graph with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and $$$m$$$ weighted edges. The graph may be disconnected. The $$$i$$$-th edge joins vertices $$$u_i$$$ and $$$v_i$$$ and has weight $$$w_i$$$.

An increasing trip of length $$$k$$$ is an ordered sequence of $$$k+1$$$ vertices $$$(x_0,x_1,\ldots,x_k)$$$ such that:

  • for every $$$0\le j \lt k$$$, vertices $$$x_j$$$ and $$$x_{j+1}$$$ are joined by an edge; and
  • for every $$$0\le j \lt k-1$$$, the weight of the edge joining $$$x_j$$$ and $$$x_{j+1}$$$ is strictly smaller than the weight of the edge joining $$$x_{j+1}$$$ and $$$x_{j+2}$$$.

The same vertex may occur more than once in a trip. Two trips are considered different if their ordered vertex sequences are different. In particular, $$$(u,v)$$$ and $$$(v,u)$$$ are different trips.

Let $$$\ell$$$ be the maximum possible length of an increasing trip. Find $$$\ell$$$ and the number of increasing trips of length $$$\ell$$$, modulo $$$998244353$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 10^5$$$, $$$1\le m\le \min\left(\frac{n(n-1)}{2},2\cdot 10^5\right)$$$), the number of vertices and edges, respectively.

The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1\le u_i \lt v_i\le n$$$, $$$1\le w_i\le 10^9$$$), describing an edge between vertices $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.

It is guaranteed that $$$(u_i,v_i)\ne(u_j,v_j)$$$ for all distinct $$$i$$$ and $$$j$$$. Different edges may have equal weights.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$w_i=1$$$ for every $$$1\le i\le m$$$.

Tests $$$2$$$–$$$3$$$ satisfy $$$n\le 8$$$.

Tests $$$4$$$–$$$5$$$ satisfy $$$m=n-1$$$, $$$u_i=i$$$, and $$$v_i=i+1$$$ for every $$$1\le i\le m$$$.

Tests $$$6$$$–$$$7$$$ satisfy $$$m=n-1$$$, $$$u_i=1$$$, and $$$v_i=i+1$$$ for every $$$1\le i\le m$$$.

Tests $$$8$$$–$$$9$$$ satisfy $$$m=n-1$$$, $$$u_i\le i$$$, and $$$v_i=i+1$$$ for every $$$1\le i\le m$$$.

Tests $$$10$$$–$$$11$$$ satisfy $$$n\le 600$$$, and all edge weights are pairwise distinct.

Tests $$$12$$$–$$$14$$$ satisfy $$$n\le 600$$$.

Tests $$$15$$$–$$$17$$$ satisfy that all edge weights are pairwise distinct.

Tests $$$18$$$–$$$20$$$ have no additional constraints. "'

Output

Output two integers $$$\ell$$$ and $$$c$$$, where $$$\ell$$$ is the length of the longest increasing trip and $$$c$$$ is the number of increasing trips of length $$$\ell$$$, modulo $$$998244353$$$.

Examples
Input
4 5
1 2 1
2 3 1
3 4 1
1 4 1
2 4 2
Output
2 4
Input
6 6
1 2 3
1 3 7
2 3 5
4 5 9
5 6 8
4 6 2
Output
3 2
Note

In the first sample, the maximum length is $$$2$$$. The four longest increasing trips are $$$(1,2,4)$$$, $$$(1,4,2)$$$, $$$(3,2,4)$$$, and $$$(3,4,2)$$$. Each has edge-weight sequence $$$(1,2)$$$.

In the second sample, the maximum length is $$$3$$$. The two longest increasing trips are $$$(1,2,3,1)$$$ and $$$(4,6,5,4)$$$, with edge-weight sequences $$$(3,5,7)$$$ and $$$(2,8,9)$$$, respectively.