// Red Knight's Shortest Path #include using namespace std; #define GET_MACRO(_1, _2, _3, NAME, ...) NAME #define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define _rep(i,n) _repl(i,0,n) #define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__) void _dbg(string){cout< void _dbg(string s,H h,T... t){int l=s.find(',');cout< ostream& operator<<(ostream &o, const pair &p){o<<"("< ostream& operator<<(ostream &o, const vector &v){o<<"[";for(T t:v){o<>n>>sx>>sy>>tx>>ty; int dx[] = {-2,-2,0,2,2,0}, dy[] = {-1,1,2,1,-1,-2}; fill(dis[0], dis[n], INF); fill(pre[0], pre[n], -1); dis[tx][ty] = 0; using P = pair; priority_queue> pq; pq.push(mp(0, mp(tx,ty))); while(!pq.empty()){ auto pp = pq.top(); pq.pop(); int x = pp.se.fi, y = pp.se.se; int d = -pp.fi; if(d > dis[x][y]) continue; rep(k,6){ int nx = x - dx[k], ny = y - dy[k]; if(nx<0 || ny<0 || nx>=n || ny>=n) continue; if(d+1 < dis[nx][ny] || (d+1 == dis[nx][ny] && pre[nx][ny] > k)){ dis[nx][ny] = d+1; pq.push(mp(-d-1, mp(nx,ny))); pre[nx][ny] = k; } } } if(dis[sx][sy] >= INF){ cout << "Impossible" << endl; return 0; } vector res; while(pre[sx][sy] != -1){ int p = pre[sx][sy]; res.pb(p); sx += dx[p]; sy += dy[p]; } string xx [] = {"UL", "UR", "R", "LR", "LL", "L"}; int m = res.size(); cout << m << endl; rep(i,m) cout << xx[res[i]] << " \n"[i==m-1]; return 0; }