Pylons.scala

import scala.io.StdIn
import scala.util.Random

object Solution extends App {

  def solve(w: Int, h: Int): Option[Vector[(Int, Int)]] = {
    val map = Array.ofDim[Boolean](h, w)

    def _trace(lastPoint: (Int, Int), acc: Vector[(Int, Int)], remains: Vector[Int]): Option[Vector[(Int, Int)]] = {
      if (remains.isEmpty) {
        Some(acc)
      } else {
        for (pos <- remains) {
          val newX = pos % w
          val newY = pos / w
          val x = lastPoint._1
          val y = lastPoint._2
          if (x != newX && y != newY && y - x != newY - newX && y + x != newY + newX && !map(newY)(newX)) {
            map(newY)(newX) = true
            _trace((newX, newY), (newX, newY) +: acc, remains.filter(_ != pos)) match {
              case Some(result) =>
                return Some(result)
              case _ =>
            }
            map(newY)(newX) = false
          }
        }
        None
      }
    }

    map(0)(0) = true
    _trace((0, 0), Vector((0, 0)), Random.shuffle((1 until (w * h)).toVector))
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { i => {
    val Array(h, w) = StdIn.readLine().split(" ").map(_.toInt)
    val answer = solve(h, w)
    answer match {
      case Some(x) =>
        println(s"Case #$i: POSSIBLE")
        println(x.map(k => s"${k._1 + 1} ${k._2 + 1}").mkString("\n"))
      case _ =>
        println(s"Case #$i: IMPOSSIBLE")
    }
  }}
}