0090. Commutative Diagram

Имя входного файла: commdiag.in
Имя выходного файла: commdiag.out
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

A special kind of diagrams, called commutative diagrams, is widely used in some branches of mathematics. More precisely, we shall call a diagram an arbitrary acyclic graph, the vertices of which are sets (as A, B,…,D in the example below) and the edges are maps between corresponding sets (for example, if we have an edge u from vertex A to vertex B, then u is a map of set A into set B). Next, if we have a path α from vertex X to vertex Y, we can define a map ã:X→Y by taking the composition of the maps which are edges of this path. For instance, the maps v'⋅u'⋅a, v'⋅b ⋅u, c⋅v⋅u : A→C' correspond to the three different paths from A to C' in the example below. A diagram is called commutative if for any two paths α and β with same origin and destination.

It is often important to check the commutativity of a given diagram. One does not need to check the condition for all pairs of α and β since some such conditions follow from some other. In the example above it is sufficient to check only four conditions: u'⋅a=b⋅u, v'⋅b=c⋅v, p⋅v'⋅u'=q and s=p⋅c. A more formal description of this situation can be done by the following rules:

Your task is to find for a given diagram a minimal set of conditions needed for the commutativity of the diagram.

Input file

The first line of the input file contains two integer numbers N – the number of vertices (1 ≤ N ≤ 100) and 1 ≤ M ≤ 1000 – the number of edges. M pairs of integers follow, each specifying source and destination vertex of the corresponding edge.

Output file

First output K – the minimal number of conditions needed for the commutativity of the diagram. Next K lines must contain some possible minimal set of conditions. Adhere to the format shown in the example.

Examples:

commdiag.incommdiag.out
7 10 1 2 2 3 1 4 2 5 3 6 4 5 5 6 3 7 4 7 6 74 3 6 = 1 4 4 7 = 2 5 6 7 10 = 9 8 = 5 10


Источник: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Обсудить       Отправить решение



Версия для печати