import Control.Monad import Control.Monad.ST import Data.List import Data.STRef import Text.Printf type Path = String data Dir st = Dir String (STRef st [Dir st]) split :: Path -> [String] split "" = [] split xs = case break ('/'==) xs of ("", _:xs) -> split xs (name, xs) -> name : split xs mkdir :: String -> ST st (Dir st) mkdir name = do children <- newSTRef [] return $ Dir name children mkdirP :: Dir st -> Path -> ST st Int mkdirP fs path = go fs (split path) where go (Dir _ children) [] = return 0 go (Dir _ children) (name:names) = do chs <- readSTRef children case find (\(Dir x _) -> name == x) chs of Nothing -> do d <- mkdir name writeSTRef children (d : chs) y <- go d names return $ y + 1 Just d -> go d names f :: [Path] -> [Path] -> ST st Int f xs ys = do root <- mkdir "/" forM_ xs (mkdirP root) liftM sum $ forM ys (mkdirP root) main :: IO () main = do t <- readLn forM_ [(1::Int)..t] $ \x -> do [n,m] <- liftM (map read . words) getLine dirs <- replicateM n getLine dirs' <- replicateM m getLine printf "Case #%d: %d\n" x (runST (f dirs dirs'))