该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小A去M国旅游。

题目描述

M国有 $n$ 个州（省），这 $n$ 个州两两有不同种类的单程航班连接。

小A有 $m$ 条旅游计划，第 $i$ 条计划是想要从第 $a_i$ 个州到第 $b_i$ 个州，小A想要在满足所有计划的情况下，坐最少种类的航班。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $a_i,b_i$。

输出格式

输出在满足所有计划的情况下，最少坐多少种航班。

样例 #1

样例输入 #1

4 5
1 2 
2 3
2 4 
3 1 
3 4

样例输出 #1

4

提示

样例解释

小A只坐 $1$ 号州到 $2$ 号州，$2$ 号州到 $3$ 号州，$2$ 号州到 $4$ 号州，$3$ 号州到 $1$ 号州的航班，就可以满足全部要求。

数据范围

对于 $30\%$ 的数据，$1 \le n,m \le 5$。

对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$1 \le a,b \le n$。