회사

플럼소프트(Plumsoft) 회사에는 직원들 사이에 위계가 있어, 어떤 직원은 다른 직원의 상사이다. 직원 $P_1 = A,\ P_2,\ \dots,\ P_k = B$ 로 이루어진 사슬이 존재하여 $P_1$ 이 $P_2$ 의 상사, $P_2$ 가 $P_3$ 의 상사, $\dots$, $P_{k-1}$ 이 $P_k$ 의 상사이면, 사람 $A$ 는 사람 $B$ 를 관리한다고 한다. 플럼소프트는 매우 건전하게 운영되는 회사이므로, 서로가 서로를 관리하는 두 직원은 존재하지 않는다고 가정할 수 있다(위계에 순환이 없다).

경영진은 회의 비용을 줄이고자, 기존의 직접적인 "$A$ 는 $B$ 의 상사" 관계 중 일부만 남기려 한다. 단, 모든 "$A$ 는 $B$ 를 관리한다" 관계는 그대로 유지되어야 한다. 누가 누구를 관리하는지 전혀 바뀌지 않도록 하면서, 남기는 직접적인 "상사" 관계의 수를 최소로 하도록 도와라.

첫째 줄에 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다 ($1 \le N \le 1000$, $1 \le M \le 10000$). $N$ 은 직원의 수, $M$ 은 회사의 직접적인 "상사" 관계의 수이다. 직원은 $1$ 번부터 $N$ 번까지 번호가 매겨져 있다. 이어지는 $M$ 개의 줄 각각에는 두 번호 $A$ 와 $B$ 가 공백으로 구분되어 주어지며, 이는 $A$ 가 $B$ 의 상사임을 뜻한다.

첫째 줄에, 모든 "관리한다" 관계가 유지되도록 남겨야 하는 직접적인 "상사" 관계의 최소 개수 $M_{min}$ 을 출력한다. 그다음 $M_{min}$ 개의 줄에, 남긴 관계들을 한 줄에 하나씩 두 번호 $A$ 와 $B$(여전히 $A$ 가 $B$ 의 상사임)를 공백으로 구분하여 출력한다. 관계는 오름차순으로, 먼저 $A$ 를 기준으로, $A$ 가 같으면 $B$ 를 기준으로 정렬하여 출력한다.