#214502. [JOISC 2017] 门票安排 / Arranging Tickets

在 JOI 共和国，有 个车站，编号从 到 。它们按顺时针方向排列在一条环形铁路上。

有 种火车票，编号从 到 。使用一张类型为 （）的票，一个人可以从车站 前往车站 ，或从车站 前往车站 。使用一张类型为 的票，一个人可以从车站 前往车站 ，或从车站 前往车站 。我们只能购买包含每种类型票各一张的票包。

你正在 JOI 共和国的一家旅行社工作。你的任务是为客户安排车票。

今天，你有 个订票请求。第 个请求表示有 人希望从车站 前往车站 。这些 人旅行时无需走相同的路线。

你希望知道，为了满足所有请求，你最少需要购买多少个票包。

任务

给定车站数量和请求信息，编写一个程序，计算你最少需要购买的票包数量。

从标准输入读取以下数据：

• 第一行包含两个由空格分隔的整数 、。表示 JOI 共和国有 个车站，今天你有 个请求。
• 接下来的 行中，第 行（）包含三个由空格分隔的整数 、、。表示第 个请求是 人希望从车站 前往车站 。

向标准输出写入一行。该行输出包含你最少需要购买的票包数量。

样例输入 1

3 3
1 2 1
2 3 1
3 1 1

样例输出 1

1

样例输入 2

3 2
1 2 4
1 2 2

样例输出 2

3

样例输入 3

6 3
1 4 1
2 5 1
3 6 1

样例输出 3

2

样例 1 解释

若所有人都顺时针旅行，则每种票各需一张，因此你只需购买一个票包。

样例 2 解释

若人们按以下方式旅行，则每种票各需三张：

• 在第一个请求中，三人顺时针旅行，一人逆时针旅行。
• 在第二个请求中，两人逆时针旅行。

因此，购买三个票包已足够。我们输出 3，因为若仅购买两个票包，则无法完成所有旅行。

样例 3 解释

例如，你购买了两个票包，并按以下方式分配：

• 将票 1、2、3 给希望从车站 1 前往车站 4 的人。
• 将票 1、6、5 给希望从车站 2 前往车站 5 的人。
• 将票 3、4、5 给希望从车站 3 前往车站 6 的人。

我们输出 2，因为若仅购买一个票包，则无法完成所有旅行。

约束条件

所有输入数据满足以下条件：

• 。
• 。
• （）。
• （）。
• （）。
• （）。

子任务

共有 5 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [10 分]

• 。
• 。
• （）。

子任务 2 [35 分]

• 。
• 。
• （）。

子任务 3 [20 分]

• 。
• 。
• （）。

子任务 4 [20 分]

• （）。

子任务 5 [15 分]

无额外约束。

翻译由 Qwen3-235B 完成