マッチングで解けるのね．

そんなの思いつきません．

解けないまま，終るのはシャクなので，Haskellで書いてみた． 

import Control.Monad
import Text.Printf
import Data.Array
import Data.Graph.Inductive
-- main part
main = do
(t:_) <- getList :: IO [Int]
forM_ [1..t] $ i -> do
(n:_) <- getList
cs <- replicateM n getList :: IO [[Int]]
printf "Case #%d: %dn" i $ solve n cs
graph :: (Ord a, Graph gr, Num t) => Int -> [[a]] -> gr () t
graph n cs = mkGraph nodes (edges ++ dummyEdges)
where nodes = [(i, ()) | i <- [..2*n+1]]
edges = [(i,n+j,1) | i <- [..n-1], j <- [..n-1], (cs!!i) `above` (cs!!j)]
dummyEdges = [(2*n,i,1) | i <- [..n-1]] ++ [(i,2*n+1,1) | i <- [n..2*n-1]]
above xs ys = and $ zipWith (<) xs ys
solve :: (Ord a) => Int -> [[a]] -> Int
solve n cs = n - maxFlow (graph n cs :: Gr () Int) (2*n) (2*n+1)
-- output and input function
getList :: Read a => IO [a]
getList = liftM (map read.words) getLine

実行時間が少し遅い気もするが気にしない．

2部グラフのマッチング→最大流

と経由．

あ，ちなみに次へは残念ながら進めませんでした．おおかたの予想通りです．