一名政府视察员即将来到你的县视察道路质量。你希望以最小的努力和开销通过视察，因此你计划带视察员在城镇之间进行一次规划好的环路旅行，以避免修缮全县所有的道路。县里的任何道路都是从一个城镇直接通往另一个城镇，且所有道路都是单向的。为了成功带视察员转一圈，你可能需要修建新的道路。请注意，禁止修建从一个城镇出发并直接返回该城镇的道路（即自环），即使是为了愚弄国家视察员，这样做也被认为是没有品位的。然而，你可以在任意两个不同的城镇之间修建任意数量、任意方向的道路。求为了能带视察员进行一次环路旅行，最少需要修建的道路数量。旅行的长度无关紧要。

输入格式

输入第一行包含两个整数：$N$ — 城镇的数量，和 $M$ — 县里单向道路的数量（$1 \le N \le 10^5$，$0 \le M \le 10^5$）。

接下来的 $M$ 行包含县里现有道路的描述。每行包含两个整数，描述一条道路：$A$ — 道路的起点城镇编号，和 $B$ — 道路的终点城镇编号（$1 \le A \neq B \le N$）。所有城镇都用 $1$ 到 $N$ 的整数进行编号。

输出格式

输出一个整数 — 为了能够带视察员在城镇之间进行一次环路旅行，最少需要修建的道路数量。如果无法做到，则输出 -1。

样例

输入样例 1

2 5
2 1
2 1
2 1
2 1
1 2

输出样例 1

0

输入样例 2

3 2
2 3
1 2

输出样例 2

1