Bilingual.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.annotation.tailrec
import scala.io.StdIn


object Main extends App {
    Console.setIn(new FileInputStream("example.in"))

    Console.setIn(new FileInputStream("C-small-practice.in"))
    Console.setOut(new FileOutputStream("C-small-practice.out"))

    case class Path(sentence: Int, visitedWord: List[String], visitedSentence: List[Integer])

    def solve(words: Vector[Array[String]]): Int = {

        def removeLinkFromWord(linkFromWord: Map[String, Vector[(String, Int)]], word:String, sentence:Int) =
            linkFromWord.map {case (x, v) => (x, v.filter(k => x != word || k._2 != sentence))}

        def removeLinkFromSentence(linkFromSentence: Map[Int, Vector[(String, Int)]], word:String, sentence:Int) =
            linkFromSentence.map {case (x, v) => (x, v.filter(k => x != sentence || k._1 != word))}

        def beginNode = Vector(Path(0, List(), List(0)))

        @tailrec
        def findPath(words: Vector[Array[String]], linkFromWord: Map[String, Vector[(String, Int)]], linkFromSentence: Map[Int, Vector[(String, Int)]], history: Vector[Path], answer: Int): Int = {
            history.find(_.sentence == 1) match {
                case Some(found) =>
                    val nextLinkFromWord = (linkFromWord /: (found.visitedWord zip found.visitedSentence.init))((acc, x) => removeLinkFromWord(acc, x._1, x._2))
                    val nextLinkFromSentence = (linkFromSentence /: (found.visitedWord zip found.visitedSentence.tail))((acc, x) => removeLinkFromSentence(acc, x._1, x._2))
                    findPath(words, nextLinkFromWord, nextLinkFromSentence, beginNode, answer + 1)
                case None =>
                    if (0 == history.length) {
                        answer
                    } else {
                        val nextHistory = for (item <- history.par;
                                             nextWord <- linkFromSentence(item.sentence) if !item.visitedWord.contains(nextWord._1);
                                             nextSentence <- linkFromWord(nextWord._1) if !item.visitedSentence.contains(nextSentence._2)
                        ) yield Path(nextSentence._2, nextWord._1 :: item.visitedWord, nextSentence._2 :: item.visitedSentence)
                        findPath(words, linkFromWord, linkFromSentence, nextHistory.toVector, answer)
                    }
            }
        }

        val intersection = words(0) intersect words(1)
        val links = words.zipWithIndex.flatMap(x => x._1.map(y => (y, x._2)))
        val linkFromWord = (links.groupBy(_._1) /: intersection)((acc, x) => removeLinkFromWord(acc, x, 1))
        val linkFromSentence = (links.groupBy(_._2) /: intersection)((acc, x) => removeLinkFromSentence(acc, x, 0))
        findPath(words, linkFromWord, linkFromSentence, beginNode, intersection.length)
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { n =>
        val c = StdIn.readLine().toInt
        val words = for (y <- 0 until c) yield StdIn.readLine().split(" ")
        println(s"Case #$n: ${solve(words.toVector)}")
    }
}