Author: | A. Baranov | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
Let there be two disjoint sets of nodes of some oriented graph: A and B.
For each node of A, set of all nodes of B reachable from it is also given.
It is known that any node of A should not have incoming edges, and that any node of B should not have outgoing edges.
There can be set of intermediate nodes C in the graph that connected with nodes from A and B.
But any two nodes from C should not be connected to each other.
You are to obtain a graph with minimal number of edges satisfying this description.
If several optimal variants exist, choose a graph with minimal number of nodes.
The answer is the number of nodes and edges in the obtained graph.
Input contains two integers: N — size of A and M — size of B,
followed by the subsets of nodes of B reachable from every node of A.
Each subset starts with a number of nodes in it (may be zero),
followed by the indices of nodes (indexing starts from zero).
Output must contain two integers: number of nodes and edges.
1≤(N,M)≤1000
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|