const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout
});

let N = 8;
let boardSize = 3;
let finalBoard = [];
let initialBoard = [];

const checkIfCompleted = (initial, final) => {
  for (let i = 0; i < boardSize; i++) {
    for (let j = 0; j < boardSize; j++) {
      if (initial[i][j] !== final[i][j]) {
        return false;
      }
    }
  }

  return true;
};

const cellDistance = (board, row, col) => {
  const boardValue = board[row][col];
  const { row: wantedRow, col: wantedCol } = findCoordinatesOfValue(
    finalBoard,
    boardValue
  );

  return boardValue === 0
    ? 0
    : Math.abs(row - wantedRow) + Math.abs(col - wantedCol);
};

const getHeuristicScore = board => {
  let sum = 0;

  for (let i = 0; i < boardSize; i++) {
    for (let j = 0; j < boardSize; j++) {
      sum += cellDistance(board, i, j);
    }
  }

  return sum;
};

const findCoordinatesOfValue = (board, value) => {
  for (let i = 0; i < boardSize; i++) {
    for (let j = 0; j < boardSize; j++) {
      if (board[i][j] === value) {
        return {
          row: i,
          col: j
        };
      }
    }
  }
};

const swapPositions = (from, board) => to => {
  const newBoard = board.map(x => x.slice());

  const temp = newBoard[from.row][from.col];
  newBoard[from.row][from.col] = newBoard[to.row][to.col];
  newBoard[to.row][to.col] = temp;

  return newBoard;
};

const getChildren = boardState => {
  const zeroCoordinates = findCoordinatesOfValue(boardState, 0);
  const swapPositionsWithZero = swapPositions(zeroCoordinates, boardState);
  const { row, col } = zeroCoordinates;

  let children = [];
  if (row !== 0) {
    const board = swapPositionsWithZero({ row: row - 1, col });
    children.push({ board, direction: "down" });
  }
  if (row !== boardSize - 1) {
    const board = swapPositionsWithZero({ row: row + 1, col });
    children.push({ board, direction: "up" });
  }
  if (col !== 0) {
    const board = swapPositionsWithZero({ row, col: col - 1 });
    children.push({ board, direction: "right" });
  }
  if (col !== boardSize - 1) {
    const board = swapPositionsWithZero({ row, col: col + 1 });
    children.push({ board, direction: "left" });
  }

  return children;
};

const DFS = (state, g, threshold, stack) => {
  const h = getHeuristicScore(state);
  const f = g + h;

  if (f > threshold) {
    return f;
  }

  if (checkIfCompleted(state, finalBoard)) {
    return -1;
  }

  const children = getChildren(state);
  let minF = Infinity;

  for (child of children) {
    stack.push(child.direction);

    const childF = DFS(child.board, g + 1, threshold, stack);

    if (childF === -1) {
      return -1;
    }

    if (childF < minF) {
      minF = childF;
    }
    stack.pop();
  }

  return minF;
};

const generateFinalBoard = (boardSize, zeroIndex) => {
  const index = zeroIndex === -1 ? boardSize * boardSize - 1 : zeroIndex;
  let nextValue = 1;

  const finalBoard = [];

  for (let i = 0; i < boardSize; i++) {
    finalBoard[i] = [];
    for (let j = 0; j < boardSize; j++) {
      finalBoard[i][j] = i * boardSize + j === index ? 0 : nextValue++;
    }
  }

  return finalBoard;
};

const main = () => {
  let threshold = getHeuristicScore(initialBoard);

  while (true) {
    const stack = [];

    const newThreshold = DFS(initialBoard, 0, threshold, stack);

    if (newThreshold === -1) {
      console.log(stack.length);
      stack.forEach(direction => console.log(direction));
      return;
    }

    threshold = newThreshold;
  }
};

let linesRead = 0;

readline.on("line", line => {
  linesRead += 1;

  if (linesRead === 1) {
    N = Number(line);
    boardSize = Math.sqrt(N + 1);
  } else if (linesRead === 2) {
    const zeroIndex = Number(line);
    finalBoard = generateFinalBoard(boardSize, zeroIndex);
  } else {
    const nextBoardLine = line.split(" ").map(Number);
    initialBoard[linesRead - 3] = nextBoardLine;
  }

  if (linesRead === boardSize + 2) {
    main();
    readline.close();
  }
});