### Matching

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

#### Problem Description

Compute the maximum cardinality matching of given undirected graph $$G$$.

#### Input

The first line contains one integer $$n$$, which denotes the number of nodes.

The following $$n$$ lines denotes the adjacency matrix $$A$$ of graph $$G$$.

($$1 \leq n \leq 100$$, $$A_{i, j} \in \{0, 1\}$$, $$A_{i, i} = 0$$, $$A_{i, j} = A_{j, i}$$)

#### Output

The only integer equals to the size of maximum cardinality matching.

#### Sample Input

3
0 1 1
1 0 1
1 1 0

#### Sample Output

1

#### Hint

One of possible matchings is to pair node $$1$$ and $$2$$, leaving node $$3$$ alone.

ftiasch

#### Manager

Information
 Solved Number 52 Submit Number 78
Problem Tags
graphs
No tag edit access