BadHorse.scala

import java.io.File
import java.io.PrintWriter

import scala.collection.mutable.ListBuffer

object BadHorse {

  val lines = io.Source.fromFile("large.in").getLines
  val printer = new PrintWriter(new File("large.out"))

  case class Turn(pairs: List[(String, String)]) {
    val players = pairs.map(t => List(t._1, t._2)).flatten.toSet.toList

    def playerSet = playerList.flatten.toSet
    def playerList = pairs.map(t => List(t._1, t._2)).toList

    def isPair(a: String, b: String): Boolean = {
      pairs.contains((a, b)) || pairs.contains((b, a))
    }

    def valid(a: String, l: List[String]): Boolean = {
      val ll = l :+ a
      if (l == Nil) {
        return true
      }
      var result = true
      l.foreach { b =>
        if (isPair(a, b)) result = false
      }
      result
    }

    def solve: String = {
      if (traverse(players, List[String](), List[String]())) "Yes" else "No"
    }

    def traverse(l: List[String], left: List[String], right: List[String]): Boolean = {

      val head = l.head

      val validLeft = valid(head, left)
      val validRight = valid(head, right)

      var res2 = false

      if (l.size == 1) { // 종료조건 
        val res = validLeft || validRight
        res2 = res
      } else {
        val bLeft = if (validLeft) traverse(l.tail, left :+ head, right) else false
        val bRight = if (validRight) traverse(l.tail, left, right :+ head) else false
        res2 = bLeft || bRight
      }

      res2
    }
  }

  def main(args: Array[String]) {
    val nOfCases = lines.next.toInt
    val turns = for {
      i <- 1 to nOfCases
      val nOfPairs = lines.next.toInt
      val pair = lines.take(nOfPairs).toList.map { line =>
        val Array(left, right) = line.split(" ")
        (left, right)
      }
    } yield {
      println(s"next: $i")
      val res = Turn(pair.toList).solve
      s"Case #$i: $res"
    }

    turns.foreach(printer.println)
    printer.flush()
  }
}