/* Sun Jul 4 09:40:34 JST 2004 */ /* Sun Jul 4 10:44:09 JST 2004 */ #include #include #include int N, M; char street[256][17]; int N_street; int adjacent[256][256]; int lookup(char s[]) { int i; for (i = 0; i < N_street; i++) { if (strcmp(street[i], s) == 0) { return i; } } return -1; } int register_street(char s[]) { int found; if ((found = lookup(s)) < 0) { strcpy(street[N_street], s); N_street++; return N_street-1; } return found; } void FloydWarshall() { int k, i, j; for (k = 0; k < N_street; k++) { for (i = 0; i < N_street; i++) { for (j = 0; j < N_street; j++) { if (adjacent[i][j] > adjacent[i][k] + adjacent[k][j]) { adjacent[i][j] = adjacent[i][k] + adjacent[k][j]; } } } } } int samelevel(int street1, int street2) { int i, cond1 = 0; if (street1 == street2) { return 0; } for (i = 0; i < N_street; i++) { if ((adjacent[street1][i] == 1 && adjacent[street2][i] == 1) || (adjacent[i][street1] == 1 && adjacent[i][street2] == 1)) { cond1 = 1; } if ((adjacent[street1][i] == 1 && adjacent[i][street2] == 1) || (adjacent[i][street1] == 1 && adjacent[street2][i] == 1)) { return 0; } } return cond1; } int main() { int i, j, street1, street2; char s[64], s1[32], s2[32]; while (1) { gets(s); N = atoi(s); if (N == 0) { break; } for (i = 0; i < 256; i++) { for (j = 0; j < 256; j++) { adjacent[i][j] = INT_MAX / 2; } } N_street = 0; for (i = 0; i < N; i++) { gets(s); strcpy(s1, strtok(s, "-")); street1 = register_street(s1); strcpy(s2, strtok(NULL, "-")); street2 = register_street(s2); adjacent[street1][street2] = 1; } printf("%d\n", N_street); for (i = 0; i < N_street; i++) { for (j = 0; j < N_street; j++) { if (samelevel(i, j)) { adjacent[i][j] = adjacent[j][i] = 0; } } } FloydWarshall(); gets(s); M = atoi(s); for (i = 0; i < M; i++) { gets(s); strcpy(s1, strtok(s, "-")); street1 = lookup(s1); strcpy(s2, strtok(NULL, "-")); street2 = lookup(s2); if (street1 >= 0 && street2 >= 0 && (adjacent[street1][street2] < INT_MAX / 2 && adjacent[street1][street2] % 2 == 1)) { printf("YES\n"); } else { printf("NO\n"); } } } return 0; }