|Submit||All submissions||Best solutions||Back to list|
COMPANY - Company
In Plumsoft company, there is a hierarchy among employees, i.e. some of them are bosses to the others. Person A is in charge of person B if there is a sequence of employees P1 = A, P2, ..., Pk = B, such that P1 is P2's boss, P2 is P3's boss, ..., and Pk-1 is Pk's boss. As Plumsoft is a pretty sane company, you can assume that no two employees can be in charge of each other. The management wants to cut the costs of meetings (they eat a lot of food), so they plan to minimize the number of "A is boss of B" relations by keeping only some of the existing ones. However they want to keep all "A is in charge of B" relations. Please, help them to successfully make this transition.
The first line of the input contains two integers N and M separated by a space character (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000). N is the number of employees, and M is the number of "boss" relations in the company. Employees are labeled with numbers 1 through N. Each of the next M lines contain two labels A and B separated by a space character, meaning that A is a boss of B.
In the first line of the output, write a single number Mmin, which is the minimum number of "boss" relations that the company has to keep. In the next Mmin lines write the relations that are kept. In each line, write two labels A and B separated by a space character, meaning that A is still a boss of B. If there are multiple solutions, write any of them. Relations can be listed in any order. Each line of the output should be followed by a newline.
Input: 5 8 3 5 1 4 4 3 1 3 4 5 1 2 1 5 2 3 Output: 5 3 5 1 4 4 3 1 2 2 3
|Cluster:||Cube (Intel G860)|
|Languages:||ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE|
|Resource:||MIT Individual Contest 2008|