BadHorse.scala

object BadHorse extends App {

  def isSplittable(pairs: List[(String, String)]): Boolean = {

    val link = ((Map.empty[String, Set[String]] withDefaultValue Set.empty[String]) /: pairs) {
      case (map, (i, j)) => map + (i -> (map(i) + j)) + (j -> (map(j) + i))
    }

    @annotation.tailrec
    def dfs(checking: List[String], checked: Map[String, Boolean]): Boolean = checking match {
      case Nil => true
      case x :: xs =>
        val (alreadyChecked, nextChecking) = link(x) partition checked.contains
        val value = if (checked contains x) checked else checked + (x -> true)
        if (alreadyChecked exists { value(_) == value(x) }) false
        else dfs(nextChecking.toList ::: xs, value ++ nextChecking.map { (_ -> !value(x)) })
    }

    dfs(link.keySet.toList, Map.empty[String, Boolean])
  }

  def process(iter: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to iter.next().toInt) {
      val m = iter.next().toInt
      val pairs = List.fill(m) {
        val Array(a, b) = iter.next() split ' '
        (a, b)
      }
      lineOut(s"Case #$i: ${if (isSplittable(pairs)) "Yes" else "No"}")
    }

  val writer = new java.io.PrintWriter("a.out")
  try {
    process(io.Source.fromFile("A-small-practice-2.in").getLines)(writer.println)
  } finally {
    writer.flush(); writer.close()
  }

}