#!/bin/python3 import sys def check(n ,i_start, j_start, i_end, j_end): chk="Possible" if(n%2==0 or n%2==1): if((i_start%2==0 and i_end%2==1) or (i_start%2==1 and i_end%2==0)): chk="Impossible" elif((i_start%2==0 and i_end%2==0)or (i_start%2==1 and i_end%2==1) ): if(j_start%2==1): p=abs(i_end-i_start)//2 if(p%2==0): if(j_end%2==0): chk="Impossible" elif(p%2==1): if(j_end%2==1): chk="Impossible" elif(j_start%2==0): p=abs(i_end-i_start)//2 if(p%2==0): if(j_end%2==1): chk="Impossible" elif(p%2==1): if(j_end%2==0): chk="Impossible" return(chk) def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. w=check(n, i_start, j_start, i_end, j_end) if(w=="Impossible"): print("Impossible") else: ad=0 hop1=abs(i_end-i_start)//2 new_i=abs(j_start-hop1) if(j_start==j_end): ad=-1 hop2=abs(new_i-j_end)//2 print(ad+hop1+hop2) p=[] if(ad==-1): while(hop1>0): if(i_start>=i_end): if(j_startj_end): p.append("UL") j_start=j_start-1 i_start=i_start-2 elif(j_start==j_end): p.append("UR") j_start=j_start+1 i_start=i_start-2 elif(i_startj_end): p.append("LL") j_start=j_start+1 i_start=i_start+2 elif(j_start==j_end): p.append("LR") j_start=j_start+1 i_start=i_start+2 hop1=hop1-1 print(*p) elif(ad!=-1): while(hop1>0): if(i_start>=i_end): if(j_startj_end): p.append("UL") j_start=j_start-1 i_start=i_start-2 elif(j_start==j_end): p.append("UR") j_start=j_start+1 i_start=i_start-2 elif(i_startj_end): p.append("LL") j_start=j_start+1 i_start=i_start+2 elif(j_start==j_end): p.append("LR") j_start=j_start+1 i_start=i_start+2 hop1=hop1-1 while(hop2>0): if(j_start>j_end): p.append("L") j_start=j_start-2 elif(j_start