import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { int n; Node start; Node end; public Solution(int n, int i_start, int j_start, int i_end, int j_end) { this.n = n; this.start = new Node("src", i_start, j_start, null); this.end = new Node("src", i_end, j_end, null); } public class Node { String pos; boolean visited = false; int i; int j; /*int ul; int ur; int ll; int lr; int l; int r;*/ Node parent; Node[] adjList = new Node[6]; public Node(String pos, int i, int j, Node parent) { this.pos = pos; this.i = i; this.j = j; this.parent = parent; } /*public addAdjNode(Node node, int pos) { this.adjList[pos] = node; }*/ } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. //String ul = "UL", ur = "UR", ll = "LL", lr = "LR", l = "L", r = "R"; Solution solution = new Solution(n, i_start, j_start, i_end, j_end); int[][] board = new int[n][n]; // each space is 0 for not visited or 1 for visited. Node src = solution.start; Node dest = solution.end; Node end = solution.pathHelper(src, dest, board); if (end == null) { System.out.println("Impossible"); } else { System.out.println(solution.countMoves(end)); System.out.print(solution.printHelper(end)); } } public int countMoves(Node node) { Node curr = node; int count = 0; while (curr.parent != null) { count++; curr = curr.parent; } return count; } public String printHelper(Node curr) { if (curr.parent.pos.equals("src")) { return curr.pos; } else { return printHelper(curr.parent) + " " + curr.pos; } } public Node pathHelper(Node src, Node dest, int[][] board) { Queue toExplore = new LinkedList(); toExplore.add(src); while (!toExplore.isEmpty()) { Node curr = (Node)toExplore.remove(); if(curr.i == dest.i && curr.j == dest.j) { return curr; // found our destination, done. } curr.visited = true; Node child; int i = curr.i; int j = curr.j; //check UL if (validateCoords(i-2, j-1, board)) { child = new Node("UL", i-2, j-1, curr); board[child.i][child.j] = 1; toExplore.add(child); } //check UR if (validateCoords(i-2, j+1, board)) { child = new Node("UR", i-2, j+1, curr); board[child.i][child.j] = 1; toExplore.add(child); } //check R if (validateCoords(i, j+2, board)) { child = new Node("R", i, j+2, curr); board[child.i][child.j] = 1; toExplore.add(child); } //check LR if (validateCoords(i+2, j+1, board)) { child = new Node("LR", i+2, j+1, curr); board[child.i][child.j] = 1; toExplore.add(child); } //check LL if (validateCoords(i+2, j-1, board)) { child = new Node("LL", i+2, j-1, curr); board[child.i][child.j] = 1; toExplore.add(child); } //check L if (validateCoords(i, j-2, board)) { child = new Node("L", i, j-2, curr); board[child.i][child.j] = 1; toExplore.add(child); } } return null; } public boolean validateCoords(int i, int j, int[][] board) { int n = board.length; if (i >= 0 && j >=0 && i < n && j < n && board[i][j] == 0) { return true; } return false; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int i_start = in.nextInt(); int j_start = in.nextInt(); int i_end = in.nextInt(); int j_end = in.nextInt(); printShortestPath(n, i_start, j_start, i_end, j_end); in.close(); } }