/* 分别对x,y,z topsort就ok了 注意有公共部分的时候的建边 */ #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <map> #include <vector> #include <cmath> #include<queue> using namespace std; int n,r; char s[3]; int x,y; int inx[1009*2]; int iny[1009*2]; int inz[1009*2]; int ansx[1009*2],ansy[1009*2],ansz[1009*2]; vector<int> vx[1009*2],vy[1009*2],vz[1009*2]; void init() { memset(inx,0,sizeof(inx)); memset(iny,0,sizeof(iny)); memset(inz,0,sizeof(inz)); for(int i=1;i<=2*n;i++) { vx[i].clear(); vy[i].clear(); vz[i].clear(); } } bool solve(int *inx,vector<int> vx[],int ansx[]) { queue<int> q; int num=0; for(int i=1;i<=2*n;i++) if(inx[i]==0) { q.push(i); } while(!q.empty()) { int x=q.front();q.pop(); ansx[x]=++num; for(int i=0;i<vx[x].size();i++) { int f=vx[x][i]; inx[f]--; if(inx[f]==0) { q.push(f); } } } if(num==2*n)return 1; return 0; } int main() { int ca=1; while(scanf("%d%d",&n,&r),n+r) { init(); for(int i=1;i<=n;i++) { vx[i].push_back(i+n); inx[i+n]++; vy[i].push_back(i+n); iny[i+n]++; vz[i].push_back(i+n); inz[i+n]++; } for(int i=0;i<r;i++) { scanf("%s%d%d",s,&x,&y); if(s[0]=='I') { vx[x].push_back(y+n); vx[y].push_back(x+n); inx[y+n]++; inx[x+n]++; vy[x].push_back(y+n); vy[y].push_back(x+n); iny[y+n]++; iny[x+n]++; vz[x].push_back(y+n); vz[y].push_back(x+n); inz[y+n]++; inz[x+n]++; } else if(s[0]=='X') { inx[y]++; vx[x+n].push_back(y); } else if(s[0]=='Y') { iny[y]++; vy[x+n].push_back(y); } else if(s[0]=='Z') { inz[y]++; vz[x+n].push_back(y); } } int flag=1; if(!solve(inx,vx,ansx)){flag=0;} if(!solve(iny,vy,ansy)){flag=0;} if(!solve(inz,vz,ansz)){flag=0;} printf("Case %d: ",ca++); if(!flag){puts("IMPOSSIBLE");puts("");continue;} { puts("POSSIBLE"); for(int i=1;i<=n;i++) { printf("%d %d %d %d %d %d\n",ansx[i],ansy[i],ansz[i],ansx[i+n],ansy[i+n],ansz[i+n]); } puts(""); } } return 0; }