409328: GYM103485 J Feedback Meetings

There are $$$n$$$ employees in the Pyramids Corporation. Some are supervisors or subordinates of others. Furthermore, there are $$$m$$$ relations, each one between two employees, called "give task". We denote this relation as $$$(u, v)$$$, meaning that $$$u$$$ gives a task to employee $$$v$$$. Observe that we may also have that $$$(v, u)$$$. That is, $$$u$$$ is not necessarily a supervisor of $$$v$$$, they can be employees in the same hierarchical level.

This enterprise has a human resource department (HR) which is separate from the $$$n$$$ employees, that is, none of the $$$n$$$ employees work on the HR department. The HR department will organize individual meetings with the employees in order to receive their complains and give feedback to them. These meetings are carried out in order, one employee at a time. There can be more than one meeting with the same employee. We consider that an employee $$$u$$$ has something to say to employee $$$v$$$ if $$$(u, v)$$$ or $$$(u, w)$$$, for some employee $$$w$$$, and $$$w$$$ has something to say to $$$v$$$. For example, if the give task relations are: $$$\{ (1,2),(2,3),(3,5),(4,2) \}$$$ then employee 1 has something to say to the employees $$$2$$$, $$$3$$$ and $$$5$$$. On the other hand, employee 3 has something to say just to employee $$$5$$$.

These meetings must be organized obeying the "feedback requirement", that states the following. If employee $$$u$$$ has something to say to employee $$$v$$$, then there must exist a meeting with $$$u$$$ before a meeting with $$$v$$$ (in this way, the HR department can give the feedback from $$$u$$$ to $$$v$$$). For example, if the give task relations are: $$$\{ (1,2),(2,1) \}$$$, then we can satisfy this requirement by organizing 3 meetings like this $$$(2, 1, 2)$$$. In other words, first a meeting with $$$2$$$ (gives his complains), after that a meeting with $$$1$$$ (receives feedback and gives his complains), and finally a meeting with $$$2$$$ again (receives feedback). In this case, this is the minimum number of meetings possible in order to satisfy the feedback requirement.

Given $$$n$$$, $$$m$$$, and the give task relations, find the minimum number of meetings needed in order to satisfy the feedback requirement.

The first line contains two integers, $$$n$$$ and $$$m$$$, that represent the number of employees and the number of relations, respectively. Each of the next $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$, that represent the relation $$$(u, v)$$$. It is guaranteed that a relation $$$(u, v)$$$ appears at most once in the input.

• $$$1 \leq n , m \leq 4 \cdot 10^5$$$
• $$$1 \leq u , v \leq n ,\, u \neq v$$$

Print an integer, the minimum number of meetings needed in order to satisfy the feedback requirement.

2 2
1 2
2 1

3

2 1
1 2

2

3 2
1 2
2 1

3