既然你身处英国，你一定想尝试一下英国美食。遗憾的是，你只有一个空闲的夜晚，所以你决定一次性尝试所有能吃到的食物。你计划享用一顿丰盛的大餐，一道接一道地品尝英国菜肴。显然，并非所有的上菜顺序都是合适的。例如，在吃完康沃尔赫瓦蛋糕（Cornish Hevva Cake）后直接吃血布丁（Blood Pudding）是不可接受的，但如果你在中间选择吃烤豆（Baked Beans），那就完全没问题了。

Hevva Cake by Caitlin on Flickr, cc by

你已经整理了一份详尽的英国菜肴清单。对于每道菜，你还决定了哪些其他菜肴适合在它之后直接食用。菜单是一个菜肴序列，使得每道菜（第一道除外）都适合在上一道菜之后直接食用。

在研究了这份菜肴清单一段时间后，你注意到了一些奇怪的事情：每当可能找到一个包含重复菜肴的菜单时（例如先吃菜肴 $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