英国菜单(British Menu)

题目描述

翻译自「NWERC2016 B题」

你想尝试英国美食。不幸的是，你只有一个晚上的空闲时间，所以你决定一次性尝试所有能吃到的食物。你计划一顿盛大的餐点，一道接一道地品尝英国菜肴。显然，不是所有的菜品顺序都是合适的。例如，在吃完蛋糕后直接吃血布丁是不可接受的，但如果你选择在中间吃烤豆，那就完全没问题。你已经编制了一份详尽的菜肴清单。对于每道菜还确定了哪些菜适合在其后直接食用。一份菜单是一系列菜品的序列，其中每道菜（除了第一道）都适合在前一道菜之后直接食用。

在研究这份菜品清单一段时间后，你注意到一个奇怪的现象：每当可以找到一个菜品出现两次的菜单时（例如先是菜品 A，然后是 B，然后是 C，然后又是菜品 A），在两次出现的相同菜品之间最多只能有四种不同类型的菜品，不包括重复出现的那道菜本身。例如，不可能找到像 A, B, C, D, E, F, A 这样的菜单，但可能找到像 A, B, C, B, C, B, C, B, C, B, A 或 A, B, C, D, E, A, B, C, D, E, A 这样的菜单。

但是谁愿意吃同一道菜两次呢？显然，你想知道在不重复任何菜品的情况下，一份菜单最多可以包含多少道菜！

输入格式

输入第一行包含整数 $n,m(1\le n \le 10^5,1\le m \le 10^6)$，分别表示菜品数量和兼容性关系的数量。

接下来的 $m$ 行，每行包含两个整数 $a,b(1\le a,b \le n)$，表示可以在菜品 $a$ 之后直接食用菜品 $b$。

菜品从 $1$ 到 $n$ 编号，编号顺序没有特殊含义，且兼容性关系满足上述约束条件。

输出格式

输出在不重复任何菜品的情况下，一份菜单最多可以包含多少道菜

样例输入 #1

4 3
1 2
2 3
2 4

样例输出 #1

3

样例输入 #2

7 7
1 2
2 3
3 4
4 5
5 2
4 6
5 7

样例输出 #2

6

数据范围

详见题目描述与输入格式中的数据规模约定。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接