Maximum All-Friend Subset Selection

In the era where ordinary people travel to outer space as casually as commuting, a class of n science students is about to embark on a space travel activity. However, not everyone gets along. For any two students, their relationship is either friendship or enmity. In other words, for any two distinct students i and j, they are either friends or enemies.

The class teacher wishes to select as many students as possible to go on the trip, under the requirement that any two selected students must be friends. Formally, if we denote the relationship between student i and student j by a value r_ij where

$$ r_{ij}=\begin{cases}1,&\text{if student }i\text{ and }j\text{ are friends},\\0,&\text{if they are enemies},\end{cases} $$

for any two distinct students in the chosen subset S it must hold that

$$\forall\, i,j\in S\ (i\neq j),\; r_{ij}=1.$$

Your task is to compute the maximum number of students that can be selected under this constraint.

inputFormat

The input starts with an integer n (the number of students). Following that are n lines, each containing n space‐separated integers. The j-th integer in the i-th line is either 1 or 0. For any two distinct indices i and j, 1 indicates that student i and student j are friends, and 0 indicates they are enemies. Note that the relationship is symmetric (i.e. the matrix is symmetric) and the diagonal elements are always 0.

outputFormat

Output a single integer, which is the maximum number of students that can be selected such that every pair among them are friends.

sample

3
0 1 0
1 0 1
0 1 0

2