C-Cheeeeen the Cute Cat_2026牛客五一集训派对day3

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

*本题于2023/8/1增强了数据，之前提交的代码不重测。

Chen loves bipartite graph matching problems. As a cat, Chen also loves playing with woolen balls. So she thinks the graph should be dense.

And here's The Cute Cat Matching Problem:
Given a bipartite graph with $2n$ nodes and $\frac{n(n-1)}{2}$ edges, guaranteed that there are no edges between nodes ${1,2,\dots,n}$ . There are no edges between nodes ${n+1,n+2,\dots,2n}$ too. Also, there's no edge between $i$ ( $1\le i\le n$ ) and $i+n$ . If there's an edge between $i$ ( $1\le i,j\le n$ ) and $j+n$ , then there will be no edge between $j$ and $i+n$ . That means the given graph guarantees that there'll be exactly one edge between $(i,j+n)$ and $(i+n,j)$ .
Help Chen find the maximum matching of the given graph.

输入描述:

The first line contains one integer  (), meanings the graph has  node.
For the next  lines, each line while contain  s, forms a  matrix  (). If , there will be an edge between node  and .

输出描述:

One integer, means the maximum matching of the given graph.

示例1

输入

复制

2
0 1
0 0

输出

复制

示例2

输入

复制

输出

复制

备注:

In the first sample, match node  and .
In the second sample, match node  and ,  and ,  and .