Company

At the Plumsoft company there is a hierarchy among employees: some employees are the boss of others. Person $A$ is in charge of person $B$ if there is a chain of employees $P_1 = A,\ P_2,\ \dots,\ P_k = B$ such that $P_1$ is $P_2$'s boss, $P_2$ is $P_3$'s boss, $\dots$, and $P_{k-1}$ is $P_k$'s boss. Plumsoft is a very well-run company, so you may assume that no two employees are each in charge of the other (the hierarchy has no cycles).

Management wants to cut the cost of meetings, so they plan to keep only some of the existing direct "$A$ is the boss of $B$" relations while preserving every "$A$ is in charge of $B$" relation. Help them keep as few direct "boss" relations as possible without changing who is in charge of whom.

The first line contains two integers $N$ and $M$ separated by a space ($1 \le N \le 1000$, $1 \le M \le 10000$), where $N$ is the number of employees and $M$ is the number of direct "boss" relations. Employees are labeled $1$ through $N$. Each of the next $M$ lines contains two labels $A$ and $B$ separated by a space, meaning $A$ is the boss of $B$.

On the first line, print a single integer $M_{min}$ — the minimum number of direct "boss" relations that must be kept so that every "in charge of" relation is preserved. Then print those $M_{min}$ relations, one per line, as two labels $A$ and $B$ separated by a space (meaning $A$ is still the boss of $B$). Print the relations in ascending order, sorted first by $A$ and then by $B$.