using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { public class Node { public int i; public int j; public IList previousMoves; public Node(int i, int j, IList previousMoves) { this.i = i; this.j = j; this.previousMoves = previousMoves; } } 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. if (Math.Abs(i_start - i_end) % 2 != 0) { Console.WriteLine("Impossible"); return; } var iDelta = i_end - i_start; var jDelta = j_end - j_start; HashSet visited = new HashSet(); Queue nextToVisit = new Queue(); nextToVisit.Enqueue(new Node(i_start, j_start, new List())); while (nextToVisit.Count > 0) { Node node = nextToVisit.Dequeue(); if (node.i == i_end && node.j == j_end) { Console.WriteLine(node.previousMoves.Count); Console.WriteLine(string.Join(" ", node.previousMoves)); return; } // control if we went too far if (iDelta > 0 && node.i > i_end || iDelta < 0 && node.i < i_end || jDelta > 0 && node.j > j_end || jDelta < 0 && node.j < j_end) { continue; } if (visited.Contains(node)) continue; visited.Add(node); // try to enqueue UL move if (iDelta <= 0 && jDelta <= 0 && node.i - 2 >= 0 && node.j - 1 >= 0 && node.previousMoves.LastOrDefault() != "LR") nextToVisit.Enqueue(new Node(node.i - 2, node.j - 1, node.previousMoves.Concat(new[] { "UL" }).ToList())); // try to enqueue UR move if (iDelta <= 0 && jDelta >= 0 && node.i - 2 >= 0 && node.j + 1 < n && node.previousMoves.LastOrDefault() != "LL") nextToVisit.Enqueue(new Node(node.i - 2, node.j + 1, node.previousMoves.Concat(new[] { "UR" }).ToList())); // try to enqueue R move if (jDelta >= 0 && node.j + 2 < n && node.previousMoves.LastOrDefault() != "L") nextToVisit.Enqueue(new Node(node.i, node.j + 2, node.previousMoves.Concat(new[] { "R" }).ToList())); // try to enqueue LR move if (iDelta >= 0 && jDelta >= 0 && node.i + 2 < n && node.j + 1 < n && node.previousMoves.LastOrDefault() != "UL") nextToVisit.Enqueue(new Node(node.i + 2, node.j + 1, node.previousMoves.Concat(new[] { "LR" }).ToList())); // try to enqueue LL move if (iDelta >= 0 && jDelta <= 0 && node.i + 2 < n && node.j - 1 >= 0 && node.previousMoves.LastOrDefault() != "UR") nextToVisit.Enqueue(new Node(node.i + 2, node.j - 1, node.previousMoves.Concat(new[] { "LL" }).ToList())); // try to enqueue L move if (jDelta <= 0 && node.j - 2 >= 0 && node.previousMoves.LastOrDefault() != "R") nextToVisit.Enqueue(new Node(node.i, node.j - 2, node.previousMoves.Concat(new[] { "L" }).ToList())); } Console.WriteLine("Impossible"); } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] tokens_i_start = Console.ReadLine().Split(' '); int i_start = Convert.ToInt32(tokens_i_start[0]); int j_start = Convert.ToInt32(tokens_i_start[1]); int i_end = Convert.ToInt32(tokens_i_start[2]); int j_end = Convert.ToInt32(tokens_i_start[3]); printShortestPath(n, i_start, j_start, i_end, j_end); } }