P1477 [NOI2008] Masquerade

The annual masquerade has begun, and Dongdong is excited to attend this year’s party. This year’s masks are specially made by the organizers. Each participant can choose a mask they like upon entry. Every mask has an ID number, and the organizer tells the wearer that number. To add mystery, the organizer divides masks into $k$ classes ($k \geq 3$). Using special techniques, the number of each mask is marked so that only people wearing a class $i$ mask can see the numbers of people wearing class $i+1$ masks, and people wearing class $k$ masks can see the numbers of people wearing class $1$ masks. Participants do not know how many classes there are, but Dongdong is very curious and wants to figure it out himself, so he starts collecting information from the crowd. The information Dongdong collects is of the form: “the wearer of mask number $a$ saw the number of mask $b$.” For example, the wearer of mask $2$ saw the number of mask $5$. Dongdong also sees some numbers himself, and he adds the corresponding information using his own mask number. Since not everyone can remember all the numbers they saw, Dongdong’s collected information may be incomplete. Please compute, based on the information Dongdong currently has, the maximum and the minimum possible numbers of mask classes. Since the organizer has declared $k \geq 3$, you must also take this into account.

The first line contains two integers $n, m$, separated by a space, where $n$ is the total number of masks prepared by the organizer, and $m$ is the number of pieces of information Dongdong collected. The next $m$ lines each contain two integers $a, b$ separated by a space, meaning the wearer of mask $a$ saw the number of mask $b$. The same pair $a, b$ may appear multiple times in the input.

Output two numbers: the first is the maximum possible number of mask classes, and the second is the minimum possible number of mask classes. If it is impossible to partition all masks into at least $3$ classes so that all the information is satisfied, print two `-1`.

- For $50\%$ of the testdata, $n \leq 300$, $m \leq 10^3$. - For $100\%$ of the testdata, $n \leq 10^5$, $m \leq 10^6$. Translated by ChatGPT 5