#include <stdio.h>#include <string.h>int reached(int, int);int map[100][100][2], n;int temp[100][100];int main(){int N, i, j, et, minimal, result;int f, t, k;char str[20];scanf("%d", &N);getchar();while(N--) {if(N == 0) {scanf("%d%d", &n, &et);for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {map[i][j][1] = 10000;map[i][j][0] = 0;}}while(scanf("%d%d", &f, &t) != EOF) {map[f][t][0] = 1;map[f][t][1] = 1;}} else {scanf("%d%d", &n, &et);getchar();for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {map[i][j][1] = 10000;map[i][j][0] = 0;}}while(gets(str) && strcmp(str, "") != 0) {f = 0;i = 0;while(i < strlen(str) && str[i] != ' ') {f *= 10;f += str[i]-'0';i++;}i++;t = 0;while(i < strlen(str)) {t *= 10;t += str[i] - '0';i++;}map[f][t][0] = 1;map[f][t][1] = 1;}}for(k = 0; k < n; k++) {for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {if(map[i][j][1] > map[i][k][1] + map[k][j][1]) {map[i][j][1] = map[i][k][1] + map[k][j][1];}}}}minimal = 100;for(i = 0; i < n; i++) {if(et == i) {continue;}if(map[i][et][1] < minimal) {for(j = 0; j < n; j++) {for(k = 0; k < n; k++) {temp[j][k] = map[j][k][0];}}if(!reached(i, et)) {minimal = map[i][et][1];result = i;}}}printf("Put guards in room %d.n", result);if(N) {printf("n");}}return 0;}int reached(int s, int e){int i, j, k;for(i = 0; i < n; i++) {temp[s][i] = 0;}for(k = 0; k < n; k++) {for(i = 0; i < n; i++) {for(j = 0; j < n; j++) {if(temp[i][k] && temp[k][j]) {temp[i][j] = 1;}}}}if(temp[0][e]) {return 1;} else {return 0;}}
