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

题目描述

作为动物学家，小 A 主要研究一些动物的食物链关系。他目前正在观测 N 只动物，将它们编号为 1 ~ N。

经过一段时间的研究，小 A 认为，这些动物可以分成 K 类（至少三类，即 K ≥ 3），每类至少有一只动物，每只动物属于且仅属于其中一类。它们之间的食物链关系形成一个环形，具体地，第 1 类动物只吃第 2 类动物，第 2 类动物只吃第 3 类动物，……，第 K-1 类动物只吃第 K 类动物，并且，第 K 类动物只吃第 1 类动物。

在小 A 观测的同时，他记录了 M 条信息，每条信息形如 x y 表示编号为 x 的动物吃编号为 y 的动物。可能存在重复信息，即多次出现相同的 x y。

现在，小 A 想知道，根据他记录的信息，这些动物最多可以分成多少类？最少可以分成多少类？即 K 可能的最大值和最小值。

如果不存在可能的 K 值，说明小 A 记录的信息有误，此时输出 -1 -1。

输入格式

第一行：两个整数 N, M

接下来 M 行，每行包含两个整数 x, y，表示编号为 x 的动物只吃编号为 y 的动物。

输出格式

一行，两个整数，分别表示 K 可能的最大值和最小值。如果不存在相应的 K 值，则输出 -1 -1。

样例1输入

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

样例1输出

3 3

样例2输入

3 4
1 2
2 3
3 2
3 1

样例2输出

-1 -1

说明/提示

50% 的数据：$1 ≤ N ≤ 300, 0 ≤ M ≤ 10^3$；

100% 的数据：$1 ≤ N ≤ 10^5, 0 ≤ M ≤ 10^6, 1 ≤ x, y ≤ N$。