P12736 [POI 2016 R2] 圣诞灯链 Christmas chain

翻译来自于 [LibreOJ](https://loj.ac/p/5032)。

**题目译自 [XXIII Olimpiada Informatyczna — II etap](https://sio2.mimuw.edu.pl/c/oi23-2/dashboard/) [Świąteczny łańcuch](https://szkopul.edu.pl/problemset/problem/cSa80AKpjHR8FlWE4BCpLGT3/statement/)** 每年圣诞节，Bajtazar 都会用五彩缤纷的灯链装点他的家。今年，他决定亲自挑选灯链的颜色，打造一串独一无二的装饰。他对灯链的美学有特定要求：某些灯链片段的颜色排列需与另一些片段完全相同。同时，他的妻子希望今年的灯链尽量丰富多彩，也就是说，灯链应包含尽可能多的不同颜色。请帮助 Bajtazar 计算，他需要购买多少种颜色的灯泡。

第一行包含两个整数 $n, m$ $(n \geq 2, m \geq 1)$，分别表示灯链中灯泡的数量和 Bajtazar 的美学要求数量。灯泡按顺序编号为 $1$ 至 $n$。 接下来的 $m$ 行描述美学要求，每行包含三个整数 $a_i, b_i, l_i$ $(1 \leq a_i, b_i, l_i; a_i \neq b_i; a_i, b_i \leq n - l_i + 1)$，表示灯链片段 $\{a_i, \ldots, a_i + l_i - 1\}$ 和 $\{b_i, \ldots, b_i + l_i - 1\}$ 应具有相同颜色。即，灯泡 $a_i$ 与 $b_i$ 颜色相同，$a_i + 1$ 与 $b_i + 1$ 颜色相同，依此类推，直至 $a_i + l_i - 1$ 与 $b_i + l_i - 1$。

输出一个正整数 $k$，表示满足所有美学要求时，灯链中可包含的最大不同颜色数。

**样例 1 解释** 设 $a, b, c$ 表示三种不同颜色的灯泡。一个满足 Bajtazar 及其妻子要求的灯链为 $\texttt{abacbababa}$。 **附加样例** 1. $n=2000, m=2$，要求片段 $\{1, \ldots, 1000\}$ 与 $\{1001, \ldots, 2000\}$ 相同，$\{1, \ldots, 500\}$ 与 $\{501, \ldots, 1000\}$ 相同，最大颜色数为 $500$。 2. $n=500000, m=499900$，第 $i$ 个要求为 $a_i=i, b_i=i+100, l_i=1$，最大颜色数为 $100$。 3. $n=80000, m=79995$，第 $i$ 个要求为 $a_i=i, b_i=i+2, l_i=4$，最大颜色数为 $2$。 4. $n=50000, m=25000$，第 $i$ 个要求为 $a_i=1, b_i=i+1, l_i=9$，灯链只能使用单一颜色。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, m \leq 2000$ | $30$ | | $2$ | $n, m \leq 500000$，所有 $l_i = 1$ | $20$ | | $3$ | $n, m \leq 80000$ | $30$ | | $4$ | $n, m \leq 500000$ | $20$ |