$$$\color{blue}{\text{LaLa}}$$$'s younger sister $$$\color{purple}{\text{LiLi}}$$$ is helping $$$\color{blue}{\text{LaLa}}$$$ cast the spirit summoning $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$.
While $$$\color{blue}{\text{LaLa}}$$$ was asleep, $$$\color{purple}{\text{LiLi}}$$$ had already built a prototype of the spirit to summon. The spirit consists of $$$N$$$ $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joints which allow any $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars attached to them to freely move around them, and $$$M$$$ $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars of various colors, each of which connects two $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joints and whose length can be adjusted to any non-negative real number before the summoning (but not after).
When it comes to spirit summoning, $$$\color{blue}{\text{LaLa}}$$$ has a far higher standard than $$$\color{purple}{\text{LiLi}}$$$. Of course, $$$\color{blue}{\text{LaLa}}$$$ was not satisfied with $$$\color{purple}{\text{LiLi}}$$$'s work whatsoever. $$$\color{blue}{\text{LaLa}}$$$ would like to fabulize the prototype by getting rid of some $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars so that
- the spirit is beautiful, which means there should not be two $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars of the same color present, and
- the spirit is as easy to control as possible, which means the degree of freedom of the spirit must be minimum over all beautiful spirits obtainable by eliminating some $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars. Note that the minimum always exists as she can always eliminate all $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars to create a beautiful spirit. See the note below for the exact definition of the degree of freedom.
Write a program that computes the degree of freedom of the spirit fabulized by $$$\color{blue}{\text{LaLa}}$$$.
The input describes the prototype spirit made by $$$\color{purple}{\text{LiLi}}$$$ and is given in the following format:
| $$$N$$$ | $$$M$$$ | |
| $$$u_0$$$ | $$$v_0$$$ | $$$c_0$$$ |
| $$$u_1$$$ | $$$v_1$$$ | $$$c_1$$$ |
| $$$\vdots$$$ | ||
| $$$u_{M-1}$$$ | $$$v_{M-1}$$$ | $$$c_{M-1}$$$ |
where $$$N$$$ is the number of $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joints, numbered from $$$0$$$ to $$$N-1$$$, $$$M$$$ is the number of $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars, and for each integer $$$0 \le i \lt M$$$, the $$$i$$$-th $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bar has color $$$c_i$$$ and connects the $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joint $$$u_i$$$ and $$$v_i$$$.
The input satisfies the following constraints:
- All the numbers in the input are integers.
- $$$2 \le N \le 200$$$
- $$$0 \le M \le 1\,000$$$
- $$$0 \le u_i \lt v_i \lt N$$$ and $$$0 \le c_i \lt M$$$ for all integers $$$0 \le i \lt M$$$
Note that there can be multiple $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars connecting the same pair of $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joints.
The output should be a single integer equal to the degree of freedom of the spirit fabulized by $$$\color{blue}{\text{LaLa}}$$$.
3 3 0 1 0 0 2 0 1 2 0
5
3 3 0 1 0 0 2 1 1 2 2
3
4 4 0 1 0 1 2 1 2 3 2 0 3 3
4
5 4 0 1 0 1 2 1 2 3 2 3 4 3
6
Intuitively, the degree of freedom is the number of axis of motions preserving edge lengths of the spirit embedded on a plane.
More formally, let $$$E$$$ be an assignment of planar coordinates (we'll call this an embedding) to all $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joints of a spirit. Note that such an embedding can be identified with an element in $$$\mathbb{R}^{2N}$$$ by concatenating all coordinates, where $$$N$$$ is the number of $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ joints.
Let $$$C(E)$$$ be the set of embeddings continuously reachable from $$$E$$$ as an element of $$$\mathbb{R}^{2N}$$$ while preserving edge lengths. i.e. for each element $$$E'$$$ of $$$C(E)$$$ and each $$$\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$$$ bars of the spirit connecting magic joints $$$u$$$ and $$$v$$$, the euclidean distance between $$$u$$$ and $$$v$$$ must be the same in $$$E$$$ and $$$E'$$$.
The degree of freedom of $$$E$$$ is the minimum non-negative integer $$$k$$$ such that there exists a continuous bijective mapping $$$F:D \rightarrow C(E)$$$ where $$$D$$$ is a connected subset of $$$\mathbb{R}^k$$$.
The degree of freedom of a spirit is the maximum degree of freedom over all such embeddings $$$E$$$.
The following illustrate the spirit fabulized by $$$\color{blue}{\text{LaLa}}$$$ along with one of the optimal embedding and the mapping $$$F$$$ for each sample tests in order.
$$$k = 5$$$, $$$D = \mathbb{R}^2 \times [0, 2\pi) \times \mathbb{R}^2$$$
$$$F: (x_0, x_1, x_2, x_3, x_4) \mapsto \langle(x_0, x_1), (x_0, x_1) + (\cos{x_2}, \sin{x_2}), (x_3, x_4)\rangle$$$
The following illustrates the 5 degrees of freedom associated with each variables.
$$$k = 3$$$, $$$D = \mathbb{R}^2 \times [0, 2\pi)$$$
$$$F: (x_0, x_1, x_2) \mapsto \langle(x_0, x_1), (x_0, x_1) + (\cos{x_2}, \sin{x_2}), (x_0, x_1) + (\cos{(\frac{\pi}{3} + x_2)}, \sin{(\frac{\pi}{3} + x_2)})\rangle$$$
The following illustrates the 3 degrees of freedom associated with each variables.
$$$k = 4$$$, $$$D = \mathbb{R}^2 \times (((0, 2] \times [0, 2\pi)) \cup (\lbrace 0 \rbrace \times [0, \pi)))$$$
$$$F: (x_0, x_1, x_2, x_3) \mapsto \langle P_0, P_0 + \frac{x_2}{2} P_1 + \sqrt{1 - \frac{x_2^2}{4}} P_2, P_0 + x_2 P_1, P_0 + \frac{x_2}{2} P_1 - \sqrt{1 - \frac{x_2^2}{4}} P_2\rangle$$$
where $$$P_0 = (x_0, x_1), P_1 = (\cos{x_3}, \sin{x_3})$$$ and $$$P_2 = (\sin{x_3}, -\cos{x_3})$$$.
The following figure on the left illustrates the 4 degrees of freedom associated with each variables. Note that the motion associated with the variable $$$x_2$$$ is non-rigid. The one on the right illustrates the motion associated with $$$x_2$$$ in detail.
$$$k = 6$$$, $$$D = \mathbb{R}^2 \times [0, 2\pi)^4$$$
$$$F: (x_0, x_1, x_2, x_3, x_4, x_5) \mapsto \langle P_0, P_1, P_2, P_3, P_4 \rangle$$$
where $$$P_0 = (x_0, x_1)$$$ and $$$P_i = P_{i-1} + (\cos{x_{i + 1}}, \sin{x_{i + 1}})$$$ for all integers $$$1 \le i \le 4$$$.
The following illustrates the 6 degrees of freedom associated with each variables.
