LaLa와 정령 소환

$\color{blue}{\text{LaLa}}$의 여동생 $\color{purple}{\text{LiLi}}$가 $\color{blue}{\text{LaLa}}$의 정령 소환 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$을 돕고 있습니다.

$\color{blue}{\text{LaLa}}$가 자는 동안 $\color{purple}{\text{LiLi}}$는 소환할 정령의 시제품을 이미 만들어 두었습니다. 이 정령은 $N$개의 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 관절과 $M$개의 서로 다른 색깔의 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대로 이루어져 있습니다. 관절에 붙은 막대는 관절을 중심으로 자유롭게 움직입니다. 각 막대는 두 관절을 잇고, 소환하기 전에는 길이를 0 이상의 임의의 실수로 조정할 수 있습니다(소환한 뒤에는 조정할 수 없습니다).

정령 소환에 관해서라면 $\color{blue}{\text{LaLa}}$의 기준은 $\color{purple}{\text{LiLi}}$보다 훨씬 높습니다. 당연히 $\color{blue}{\text{LaLa}}$는 $\color{purple}{\text{LiLi}}$의 작업에 조금도 만족하지 않았습니다. $\color{blue}{\text{LaLa}}$는 다음 조건을 만족하도록 일부 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대를 제거해서 시제품을 완성하려고 합니다.

1. 정령이 아름다워야 합니다. 즉, 같은 색의 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대가 두 개 이상 남아 있으면 안 됩니다.
2. 정령이 최대한 조종하기 쉬워야 합니다. 즉, 일부 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대를 제거하여 만들 수 있는 모든 아름다운 정령 중에서 자유도가 최소여야 합니다. 모든 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대를 전부 제거하면 아름다운 정령이 되므로 최솟값은 항상 존재합니다. 자유도의 정확한 정의는 아래 주석을 참고하세요.

$\color{blue}{\text{LaLa}}$가 완성한 정령의 자유도를 계산하는 프로그램을 작성하세요.

입력은 $\color{purple}{\text{LiLi}}$가 만든 시제품 정령을 나타내며, 다음 형식으로 주어집니다.

$N$ $M$

$u\_0$ $v\_0$ $c\_0$

$u\_1$ $v\_1$ $c\_1$

$\vdots$

$u\_{M-1}$ $v\_{M-1}$ $c\_{M-1}$

여기서 $N$은 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 관절의 개수이며 0부터 $N-1$까지 번호가 매겨집니다. $M$은 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대의 개수입니다. 각 정수 $0 \le i < M$에 대해 $i$번째 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대의 색은 $c\_i$이고, 관절 $u\_i$와 $v\_i$를 잇습니다.

입력은 다음 제약을 만족합니다.

• 입력의 모든 수는 정수입니다.
• $2 \le N \le 200$
• $0 \le M \le 1\,000$
• 모든 정수 $0 \le i < M$에 대해 $0 \le u\_i < v\_i < N$이고 $0 \le c\_i < M$입니다.

같은 두 관절을 잇는 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대가 여러 개 있을 수 있습니다.

$\color{blue}{\text{LaLa}}$가 완성한 정령의 자유도와 같은 정수 하나를 출력합니다.

직관적으로, 자유도는 평면에 놓인 정령에서 막대의 길이를 유지하는 운동 축의 개수입니다.

더 엄밀하게 말하면, $E$를 정령의 모든 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 관절에 평면 좌표를 할당한 것이라고 합니다(이를 배치라고 부릅니다). 이런 배치는 모든 좌표를 이어 붙여 $\mathbb{R}^{2N}$의 원소로 볼 수 있습니다. 여기서 $N$은 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 관절의 개수입니다.

$C(E)$는 막대 길이를 유지하면서 $\mathbb{R}^{2N}$ 안에서 $E$로부터 연속적으로 도달할 수 있는 배치들의 집합입니다. 즉, $C(E)$의 각 원소 $E'$와 관절 $u$, $v$를 잇는 각 $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ 막대에 대해, $u$와 $v$ 사이의 유클리드 거리는 $E$와 $E'$에서 같아야 합니다.

배치 $E$의 자유도는 연속인 전단사 함수 $F:D \rightarrow C(E)$가 존재하는 가장 작은 음이 아닌 정수 $k$입니다. 여기서 $D$는 $\mathbb{R}^k$의 연결된 부분집합입니다.

정령의 자유도는 이런 모든 배치 $E$에 대한 자유도 중 최댓값입니다.

아래는 $\color{blue}{\text{LaLa}}$의 정령과 각 예제에 대해 최적 배치 하나 및 사상 $F$를 차례로 보여줍니다.

1. $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$

   아래 그림은 각 변수에 대응하는 5개의 자유도를 보여줍니다.

   

2. $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$

   아래 그림은 각 변수에 대응하는 3개의 자유도를 보여줍니다.

   

3. $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$

   여기서 $P\_0 = (x\_0, x\_1)$, $P\_1 = (\cos{x\_3}, \sin{x\_3})$, $P\_2 = (\sin{x\_3}, -\cos{x\_3})$입니다.

   왼쪽 그림은 각 변수에 대응하는 4개의 자유도를 보여줍니다. 변수 $x\_2$에 대응하는 운동은 강체 운동이 아닙니다. 오른쪽 그림은 $x\_2$에 대응하는 운동을 자세히 보여줍니다.

   

4. $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$

   여기서 $P\_0 = (x\_0, x\_1)$이고, 모든 정수 $1 \le i \le 4$에 대해 $P\_i = P\_{i-1} + (\cos{x\_{i + 1}}, \sin{x\_{i + 1}})$입니다.

   아래 그림은 각 변수에 대응하는 6개의 자유도를 보여줍니다.