русский
english
0090. Commutative Diagram
| Input file name: | commdiag.in |
| Output file name: | commdiag.out |
| Time limit: | 2 s |
| Memory limit: | 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.in | commdiag.out |
|---|---|
| 7 10 1 2 2 3 1 4 2 5 3 6 4 5 5 6 3 7 4 7 6 7 | 4 3 6 = 1 4 4 7 = 2 5 6 7 10 = 9 8 = 5 10 |
Source: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08
Discuss Submit a solution
Printable version