Rainbow Graph

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given an undirected compete graph with n nodes. Each edge can be one of n*(n1)/2 +1 different colors. These colors are labeled from 0 to n*(n1)/2, inclusive. But not all these n*(n1)/2 +1 colors need to be used. ie. it is possible that two different edges could have the same color. Formally, let c_{i,j} denote the color between the ith and jth nodes. (Note that these edges are undirected, so c_{i,j} = c_{j,i}). We will define c_{i,i} to be zero, although there is no such edge present. i.e. the graph does not contain selfloops.
A subset of nodes is called interesting if every node in the subset has at least two edges of different colors, connecting it to vertices in the subset.
Your task is to determine the maximum possible size of an interesting subset of nodes.
Note that, by definition, the empty subset of nodes is an interesting subset, and so the answer is always at least zero.
Input
The first line of input will contain an integer T, the number of test cases.
Each test case will be formatted as follows:
The first line will contain a single integer n.
The next n lines will contain n integers each. The jth integer on the ith line will denote c_{i,j}.
Output
For each test case, output the maximum possible size of an interesting subset, in a new line.
Constraints
 1 ≤ T ≤ 100
 1 ≤ n ≤ 50
 0 ≤ c_{i,j} ≤ n*(n1)/2
 if i = j then c_{i,j} = 0
 c_{i,j} = c_{j,i}
Example
Input: 4 3 0 1 2 1 0 3 2 3 0 3 0 1 1 1 0 3 1 3 0 2 0 1 1 0 6 0 9 2 4 7 8 9 0 9 9 7 9 2 9 0 3 7 6 4 9 3 0 7 1 7 7 7 7 0 7 8 9 6 1 7 0 Output: 3 0 0 4
Explanation
In the first case, the set of all nodes is an interesting subset.
In the second and third cases, no nonempty subset of nodes is interesting.
In the last case, an interesting subset of nodes is {1,3,4,6}. There is no larger interesting subset.
Author:  lg5293 
Tester:  errichto 
Editorial  https://discuss.codechef.com/problems/RAINBOW 
Tags  cook80, easymedium, graph, greedy, lg5293 
Date Added:  13032017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions