#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace __gnu_pbds; #define all(x) (x).begin(), (x).end() #define pb push_back #define eb emplace_back #define xx first #define yy second #define sz(x) (int)(x).size() #define gc getchar #define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define mp make_pair #ifndef ONLINE_JUDGE # define LOG(x) (cerr << #x << " = " << (x) << endl) #else # define LOG(x) ((void)0) #endif using ll = long long; using ull = unsigned long long ; using ld = long double ; using str = string; using ordered_set=tree, null_type, less>, rb_tree_tag, tree_order_statistics_node_update>; const double PI=acos(-1); const ll INF = 1LL<<62; const ll MINF = -(1LL<<62); template T getint() { T val=0; char c; bool neg=false; while((c=gc()) && !(c>='0' && c<='9')) { neg|=c=='-'; } do { val=(val*10)+c-'0'; } while((c=gc()) && (c>='0' && c<='9')); return val*(neg?-1:1); } //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution(0, n-1)(rng) vector G[20001]; int n; char exc; string t[101]; vector, pair>> ans; int st[20001]; pair dfs(int x) { st[x]=1; int xx=x/n, yy=x%n; for(int i:G[x]) { if(!st[i]) { auto from=dfs(i); ans.pb({from, {xx,yy}}); } } return {xx,yy}; } struct dsu { vector par; vector sz; dsu(int n) : par(n,-1) {sz.assign(n,1);} int get(int x) { if(par[x]==-1) return x; return par[x]=get(par[x]); } bool merge(int x, int y) { int px=get(x), py=get(y); if(px==py) return false; if(sz[px]>sz[py]) { swap(px,py); swap(x,y); //:) lyft } sz[py]+=sz[px]; par[px]=py; //~ LOG(x); //~ LOG(y); G[x].pb(y); G[y].pb(x); return true; } }; dsu ds(1); map>> d={ {'K', {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}}, {'N', {{-1,-2},{-1,2},{1,2},{1,-2},{-2,-1},{2,-1},{2,1},{-2,1}}}, }; bool valid(int x, int y) { return x>=0 && y>=0 && x>n>>exc; for(int i=0;i>t[i]; ds=dsu(n*n); for(int i=0;i dd:d[exc]) { int ni=i+dd.xx, nj=j+dd.yy; if(valid(ni, nj) && t[ni][nj]==t[i][j]) { ds.merge(conv(i,j), conv(ni, nj)); } } }else assert(0); } } } set s; for(int i=0;i1 || sz(s)==0) { cout<<"NO\n"; return 0; } dfs(*s.begin()); cout<<"YES\n"; for(auto i:ans) { cout<