## Problem G. Graph minimization ≡

• problems
• en ru
 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.070s 0.009s 13