Problem G. Graph minimization

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

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 format

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 format

Output must contain two integers: number of nodes and edges.

Constraints

1 ≤ (N, M) ≤ 1000

Sample tests

No. Standard input Standard output
1
5 4

4 0 1 2 3
4 1 0 3 2
4 3 1 0 2
4 0 3 2 1
4 3 2 1 0
10 9
2
5 4

2 1 0
2 0 2
2 2 3
2 3 0
2 0 1
9 10

0.074s 0.011s 13