由于恐怖主义威胁日益严重，拜特兰防御局（ADB）决定针对袭击事件制定行动计划。该机构的关键任务是确保在发生轰炸时，拜特兰国王能够迅速撤离。

皇宫位于拜特兰首都的某个路口旁。在另一个路口旁设有避难所，一旦发生威胁，国王应立即被转移至此。该机构拥有首都精确的道路网络规划图，由路口和连接路口的单向街道组成。

如果一条撤离路线包含的街道数量不超过 三 条，则被认为是快速撤离路线。如果某条街道遭到轰炸，皇家车队将无法通行。ADB 要求你计算：为了使国王没有任何快速撤离路线，最少需要轰炸多少条街道。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 1\,000$, $0 \le m \le n(n-1)$)，分别表示拜特兰首都的路口数量和街道数量。路口编号从 $1$ 到 $n$；皇宫位于 $1$ 号路口旁，避难所位于 $n$ 号路口旁。

接下来的 $m$ 行包含街道的描述。其中第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示一条从 $a_i$ 号路口出发并到达 $b_i$ 号路口的单向街道。对于每一对有序路口，最多存在一条从前者指向后者的街道。

输出格式

你的程序应向标准输出写入一个整数，即为了使国王没有任何快速撤离路线，恐怖分子最少需要轰炸的街道数量。

样例

输入 1

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

输出 1

2

为了使国王没有任何快速撤离路线，只需轰炸街道 $1 \to 3$ 和 $3 \to 5$（在上图中被划掉）。