import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { static class Node{ int i,j,n; String name; Node p; public Node(int i, int j, int n, String s, Node p) { // TODO Auto-generated constructor stub this.i = i; this.j = j; this.n = n; this.name = s; this.p = p; } public ArrayList getNext(){ ArrayList nodes = new ArrayList<>(); if(i - 2 >= 0 && j - 1 >= 0) { nodes.add(new Node(i-2, j-1, n, "UL", this)); } if(i -2 >=0 && j +1 =0) { nodes.add(new Node(i+2, j -1, n, "LL", this)); } if(j - 2 >= 0) { nodes.add(new Node(i, j-2, n, "L", this)); } return nodes; } public Node parent() { // TODO Auto-generated constructor stub return p; } @Override public int hashCode() { // TODO Auto-generated method stub return (i + "+" + j).hashCode(); } @Override public String toString() { // TODO Auto-generated method stub return i + "+" + j; } @Override public boolean equals(Object obj) { // TODO Auto-generated method stub return this.i == ((Node)obj).i && this.j == ((Node)obj).j; } } 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. HashSet nodes = new HashSet<>(); Queue vists = new LinkedList<>(); Node start = new Node(i_start, j_start, n, null, null); Node end = new Node(i_end, j_end, n, null, null); nodes.add(start.toString()); vists.add(start); while(!vists.isEmpty()) { Node t = (Node)vists.poll(); if(t.equals(end)) { print(t); return; } ArrayList ns = t.getNext(); for(Node nod : ns) { if(!nodes.contains(nod.toString())) { nodes.add(nod.toString()); vists.add(nod); } } } System.out.println("Impossible"); } public static void print(Node t) { ArrayList rout = new ArrayList<>(); while (t.parent() != null) { if(t.name != null) { rout.add(t.name); } t = t.p; } System.out.println(rout.size()); for(int i = rout.size() - 1; i >=0; i--) { System.out.print(rout.get(i) + " "); } System.out.println(); } 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(); } }