#include
const int maxn = 1e3+7, maxm = 2e4+7;
int v[maxm], col[maxn], vis[maxn], head[maxn], nxt[maxm];
int n, m, k, tot, pos;
void addedge(int x, int y){
v[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int u){
pos++;
for(int i = head[u]; i; i = nxt[i]){
if(col[v[i]]){
//printf("pos : %d ", pos);
//printf("near %d is %d\n", u, v[i]);
vis[col[v[i]]] = pos;
}
}
for(int i = 1; ; i++){
if(vis[i] < pos){
col[u] = i;
//printf("pos : %d ", pos);
//printf("give %d color %d\n", u, i);
break;
}
}
for(int i = head[u]; i; i = nxt[i]){
//printf("%d %d %d col v i %d\n", pos, i, v[i], col[v[i]]);
if(!col[v[i]])
dfs(v[i]);
}
}
void solve(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++)
col[i] = head[i] = vis[i] = 0;
pos = tot = 0;
while(m--){
int x, y;
scanf("%d%d", &x, &y);
addedge(x, y);
addedge(y, x);
}
for(int i = 1; i <= n; i++){
if(!col[i])
dfs(i);
}
int x = 0;
bool flag = 1;
for(int i = 1; i <= n; i++){
if(col[i] > k){
x = i;
flag = 0;
break;
}
}
/*for(int i = 1; i <= n; i++)
printf(" %d", col[i]);
puts("color");*/
if(flag){
printf("coloring");
for(int i = 1; i <= n; i++)
printf(" %d", col[i]);
return;
}
printf("path");
int loop = k;
printf(" %d", x);
while(loop){
for(int i = head[x]; i; i = nxt[i]){
if(col[v[i]] == loop){
x = v[i];
break;
}
}
printf(" %d", x);
loop--;
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
solve();
puts("");
}
return 0;
}
/*
1
5 10 4
1 2 2 3 3 4 4 5 5 1 1 3 1 4 2 5 4 2 3 5
*/