#include using namespace std; #define FOR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define pb emplace_back #define x first #define y second #define all(x) x.begin(), x.end() #define argmax(a) (max_element(all(a)) - (a).begin()) #define argmin(a) (min_element(all(a)) - (a).begin()) #define dbg(args...) {err(split(#args,',').begin(),args);} #define tthti template inline #define ttt12i template inline #define ttti template inline inline void wr2(){cout<<"\n";} inline void wr() {cout<<"\n";} inline void rd() {} ttti void read(T &a); ttti void priws(T a); ttti void print(T a); void err(vector::iterator it){++it;} tthti void rd (Head& head,Tail&... tail){read(head); rd (tail...);} tthti void wr2(Head head, Tail... tail){print(head);wr2(tail...);} tthti void wr(Head head, Tail... tail){priws(head);wr2(tail...);} ttti void wr_range(T f,T s){priws(*f);for(auto i=++f;i!=s;++i)print(*i);} tthti void err(vector::iterator it,Head head,Tail...tail){wr((*it).substr((*it)[0]==' ',INT_MAX),"=",head);err(++it, tail...);} vectorsplit(const string&s,char c){vectorv;stringstream ss(s);string x;while(getline(ss,x,c))v.pb(x);return move(v);} #define a _a #define n _n ttt12i istream&operator>>(istream&is,pair&a){return is>>a.first>>a.second;} ttt12i ostream&operator<<(ostream&os,pair&a){return os<&a){os<::value]<>(istream&is,vector&a){if(a.size()==0){int n;is>>n;a.resize(n);}for(int i=0;i>a[i];return is;} ttti void print(T a){cout<<" "<>a;} typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector > vvi; typedef vector vl; typedef vector > vvl; /*----------------------------------------------------------------------------------------------------*/ vector moves={{-2, -1}, {-2, 1}, {0, 2}, {2, 1}, {2, -1}, {0, -2}}; vector ms={"UL", "UR", "R", "LR", "LL", "L"}, res; int n; pii st, en; vector > v; vvi vs; vvi vis; bool isval(pii cl){ return cl.x>=0 && cl.x=0 && cl.y q; q.push(st); vis[st.x][st.y]=1; while(!q.empty()){ pii cl=q.front(); q.pop(); // wr(cl.x, cl.y); if(cl==en){ return true; } FOR(i, 0, 6){ pii nxt=make_pair(cl.x+moves[i].x, cl.y+moves[i].y); if(isval(nxt) && !vis[nxt.x][nxt.y]){ vis[nxt.x][nxt.y]=1; vs[nxt.x][nxt.y]=i; v[nxt.x][nxt.y]=cl; q.push(nxt); } } // c++; } return false; } void path(){ pii cl=en; while(cl!=st){ // cout<(n)); vis.resize(n, vi(n, 0)); vs.resize(n, vi(n)); if(bfs()){ path(); int l=(int)res.size(); cout<