#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
#define hash 1024
int cityEdge[1004][5] = {};
int shortPath[10][2000][1004] = {}, pathNum;
int visited[1004] = {};
int storeEdge[20000] = {};
int queue[1004] = {}, head, tail, edgeNum;
int stack[1004] = {}, top;
int outputStack[1004] = {}, con, endss;
void outputstack(int station, int pos){
if(station == con - 1){
for(int i = 0; i < pos; i++){
printf("%d ", outputStack[i]);
}
printf("%d\n", endss);
}else{
for(int i = 1; i <= shortPath[station][0][0]; i++){
for(int j = 1; j <= shortPath[station][0][1] + 1; j++){
outputStack[pos+j-1] = shortPath[station][i][j];
}
outputstack(station + 1, pos + shortPath[station][0][1]);
}
}
}
using namespace std;
int cmp(const void *a, const void *b){
int* aa = (int*)a;
int* bb = (int*)b;
if(*aa > *bb) return 1;
else return -1;
}
int cmp2(const void *a, const void *b){
int *aa = (int *)a;
int *bb = (int *)b;
for(int i = 1; ;i ++){
if(aa[i] > bb[i]) return 1;
if(aa[i] < bb[i]) return -1;
}
}
void DFS(int end, int station, int depth){
stack[top++] = end;
if(depth > 0){
int low = lower_bound(storeEdge, storeEdge+edgeNum, end * hash) - storeEdge;
int upp = upper_bound(storeEdge, storeEdge+edgeNum, (end+1) * hash) - storeEdge;
for(int i = low; i < upp; i++){
DFS(storeEdge[i] % hash, station, depth - 1);
}
top--;
}else{
pathNum ++;
for(int i = 0; i < top; i++){
shortPath[station][pathNum][top-i] = stack[i];
}
top--;
return;
}
}
void BFS(int start, int end, int station){
memset(visited, -1, sizeof(int) * 1004);
memset(storeEdge, 0, sizeof(int) * 20000);
head = edgeNum = 0;
tail = 1;
queue[0] = start, visited[start] = 0;
while(head != tail && visited[end] == -1){
int tmp = queue[head++];
for(int i = 1; i <= cityEdge[tmp][0]; i++){
if(visited[cityEdge[tmp][i]] != -1){
if(visited[cityEdge[tmp][i]] == visited[tmp] + 1)
storeEdge[edgeNum++] = cityEdge[tmp][i] * hash + tmp;
continue;
}
visited[cityEdge[tmp][i]] = visited[tmp] + 1;
storeEdge[edgeNum++] = cityEdge[tmp][i] * hash + tmp;
queue[tail++] = cityEdge[tmp][i];
}
}
assert(head!=tail);
int tmp = queue[head++];
while(visited[end] == visited[tmp] + 1){
for(int i = 1; i <= cityEdge[tmp][0]; i++){
if(cityEdge[tmp][i] == end){
storeEdge[edgeNum++] = cityEdge[tmp][i] * hash + tmp;
}
}
if(head == tail) break;
tmp = queue[head++];
}
qsort(storeEdge, edgeNum, sizeof(int), cmp);
memset(stack, 0, sizeof(int) * 1004);
top = 0, pathNum = 0;
DFS(end, station, visited[end]);
shortPath[station][0][0] = pathNum;
shortPath[station][0][1] = visited[end];
for(int i = 1; i <= pathNum; i++){
qsort(&shortPath[station][1], pathNum, sizeof(int)*1004, cmp2);
}
}
int main(){
int cityNum, nightNum;
scanf("%d %d", &cityNum, &nightNum);
for(int i = 1; i <= cityNum; i++){
int city, tmp, connected = 0;
char ch;
scanf("%d", &tmp);
while(scanf("%d%c", &city, &ch) != EOF){
cityEdge[tmp][++connected] = city;
if(ch == '\n') break;
}
cityEdge[tmp][0] = connected;
qsort(cityEdge[tmp] + 1, connected, sizeof(int), cmp);
}
for(int i = 1; i <= nightNum; i++){
memset(shortPath, 0, sizeof(int) * 10 * 500 * 1004);
printf("Night %d:\n", i);
int cityConnected[10];
int city, connected = 0;
char ch;
while(scanf("%d%c", &city, &ch) != EOF){
cityConnected[++connected] = city;
if(ch == '\n') break;
}
for(int i = 1; i < connected; i++){
//printf("%d %d:\n", cityConnected[i], cityConnected[i+1]);
BFS(cityConnected[i], cityConnected[i+1], i-1);
}
int len = 0;
int path = 1;
for(int i = 1; i < connected; i++){
path *= shortPath[i-1][0][0];
len += shortPath[i-1][0][1];
}
printf("Possible ways: %d\nNumber of stations: %d\n", path, len + 1);
puts("Path:");
con = connected;
endss = cityConnected[connected];
memset(outputStack, 0, sizeof(int) * 1004);
outputStack[0] = cityConnected[1];
outputstack(0, 0);
puts("");
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGFzc2VydC5oPgojZGVmaW5lIGhhc2ggMTAyNAoKaW50IGNpdHlFZGdlWzEwMDRdWzVdID0ge307CmludCBzaG9ydFBhdGhbMTBdWzIwMDBdWzEwMDRdID0ge30sIHBhdGhOdW07CmludCB2aXNpdGVkWzEwMDRdID0ge307CmludCBzdG9yZUVkZ2VbMjAwMDBdID0ge307CmludCBxdWV1ZVsxMDA0XSA9IHt9LCBoZWFkLCB0YWlsLCBlZGdlTnVtOwppbnQgc3RhY2tbMTAwNF0gPSB7fSwgdG9wOwppbnQgb3V0cHV0U3RhY2tbMTAwNF0gPSB7fSwgY29uLCBlbmRzczsKCnZvaWQgb3V0cHV0c3RhY2soaW50IHN0YXRpb24sIGludCBwb3MpewoJaWYoc3RhdGlvbiA9PSBjb24gLSAxKXsKCQlmb3IoaW50IGkgPSAwOyBpIDwgcG9zOyBpKyspewoJCQlwcmludGYoIiVkICIsIG91dHB1dFN0YWNrW2ldKTsKCQl9CgkJcHJpbnRmKCIlZFxuIiwgZW5kc3MpOwoJfWVsc2V7CgkJZm9yKGludCBpID0gMTsgaSA8PSBzaG9ydFBhdGhbc3RhdGlvbl1bMF1bMF07IGkrKyl7CgkJCWZvcihpbnQgaiA9IDE7IGogPD0gc2hvcnRQYXRoW3N0YXRpb25dWzBdWzFdICsgMTsgaisrKXsKCQkJCW91dHB1dFN0YWNrW3BvcytqLTFdID0gc2hvcnRQYXRoW3N0YXRpb25dW2ldW2pdOwoJCQl9CgkJCW91dHB1dHN0YWNrKHN0YXRpb24gKyAxLCBwb3MgKyBzaG9ydFBhdGhbc3RhdGlvbl1bMF1bMV0pOwoJCX0KCX0KCQp9Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGNtcChjb25zdCB2b2lkICphLCBjb25zdCB2b2lkICpiKXsKCWludCogYWEgPSAoaW50KilhOwoJaW50KiBiYiA9IChpbnQqKWI7CglpZigqYWEgPiAqYmIpIHJldHVybiAxOwoJZWxzZSByZXR1cm4gLTE7Cn0KCmludCBjbXAyKGNvbnN0IHZvaWQgKmEsIGNvbnN0IHZvaWQgKmIpewoJaW50ICphYSA9IChpbnQgKilhOwoJaW50ICpiYiA9IChpbnQgKiliOwoJZm9yKGludCBpID0gMTsgO2kgKyspewoJCWlmKGFhW2ldID4gYmJbaV0pIHJldHVybiAxOwoJCWlmKGFhW2ldIDwgYmJbaV0pIHJldHVybiAtMTsKCX0KfQoKCnZvaWQgREZTKGludCBlbmQsIGludCBzdGF0aW9uLCBpbnQgZGVwdGgpewoJc3RhY2tbdG9wKytdID0gZW5kOwoJaWYoZGVwdGggPiAwKXsKCQlpbnQgbG93ID0gbG93ZXJfYm91bmQoc3RvcmVFZGdlLCBzdG9yZUVkZ2UrZWRnZU51bSwgZW5kICogaGFzaCkgLSBzdG9yZUVkZ2U7CgkJaW50IHVwcCA9IHVwcGVyX2JvdW5kKHN0b3JlRWRnZSwgc3RvcmVFZGdlK2VkZ2VOdW0sIChlbmQrMSkgKiBoYXNoKSAtIHN0b3JlRWRnZTsKCQlmb3IoaW50IGkgPSBsb3c7IGkgPCB1cHA7IGkrKyl7CgkJCURGUyhzdG9yZUVkZ2VbaV0gJSBoYXNoLCBzdGF0aW9uLCBkZXB0aCAtIDEpOwoJCX0KCQl0b3AtLTsKCX1lbHNlewoJCXBhdGhOdW0gKys7CgkJZm9yKGludCBpID0gMDsgaSA8IHRvcDsgaSsrKXsKCQkJc2hvcnRQYXRoW3N0YXRpb25dW3BhdGhOdW1dW3RvcC1pXSA9IHN0YWNrW2ldOwoJCX0KCQl0b3AtLTsKCQlyZXR1cm47Cgl9Cgp9Cgp2b2lkIEJGUyhpbnQgc3RhcnQsIGludCBlbmQsIGludCBzdGF0aW9uKXsKCW1lbXNldCh2aXNpdGVkLCAtMSwgc2l6ZW9mKGludCkgKiAxMDA0KTsKCW1lbXNldChzdG9yZUVkZ2UsIDAsIHNpemVvZihpbnQpICogMjAwMDApOwoJaGVhZCA9IGVkZ2VOdW0gPSAwOwoJdGFpbCA9IDE7CglxdWV1ZVswXSA9IHN0YXJ0LCB2aXNpdGVkW3N0YXJ0XSA9IDA7Cgl3aGlsZShoZWFkICE9IHRhaWwgJiYgdmlzaXRlZFtlbmRdID09IC0xKXsKCQlpbnQgdG1wID0gcXVldWVbaGVhZCsrXTsKCQlmb3IoaW50IGkgPSAxOyBpIDw9IGNpdHlFZGdlW3RtcF1bMF07IGkrKyl7CgkJCWlmKHZpc2l0ZWRbY2l0eUVkZ2VbdG1wXVtpXV0gIT0gLTEpewoJCQkJaWYodmlzaXRlZFtjaXR5RWRnZVt0bXBdW2ldXSA9PSB2aXNpdGVkW3RtcF0gKyAxKQoJCQkJCXN0b3JlRWRnZVtlZGdlTnVtKytdID0gY2l0eUVkZ2VbdG1wXVtpXSAqIGhhc2ggKyB0bXA7CgkJCQljb250aW51ZTsKCQkJfQoJCQl2aXNpdGVkW2NpdHlFZGdlW3RtcF1baV1dID0gdmlzaXRlZFt0bXBdICsgMTsKCQkJc3RvcmVFZGdlW2VkZ2VOdW0rK10gPSBjaXR5RWRnZVt0bXBdW2ldICogaGFzaCArIHRtcDsKCQkJcXVldWVbdGFpbCsrXSA9IGNpdHlFZGdlW3RtcF1baV07CgkJfQoJfQoJYXNzZXJ0KGhlYWQhPXRhaWwpOwoJaW50IHRtcCA9IHF1ZXVlW2hlYWQrK107Cgl3aGlsZSh2aXNpdGVkW2VuZF0gPT0gdmlzaXRlZFt0bXBdICsgMSl7CgkJZm9yKGludCBpID0gMTsgaSA8PSBjaXR5RWRnZVt0bXBdWzBdOyBpKyspewoJCQlpZihjaXR5RWRnZVt0bXBdW2ldID09IGVuZCl7CgkJCQlzdG9yZUVkZ2VbZWRnZU51bSsrXSA9IGNpdHlFZGdlW3RtcF1baV0gKiBoYXNoICsgdG1wOwoJCQl9CgkJfQoJCWlmKGhlYWQgPT0gdGFpbCkgYnJlYWs7IAoJCXRtcCA9IHF1ZXVlW2hlYWQrK107Cgl9CgkKCQoJcXNvcnQoc3RvcmVFZGdlLCBlZGdlTnVtLCBzaXplb2YoaW50KSwgY21wKTsKCgltZW1zZXQoc3RhY2ssIDAsIHNpemVvZihpbnQpICogMTAwNCk7Cgl0b3AgPSAwLCBwYXRoTnVtID0gMDsKCURGUyhlbmQsIHN0YXRpb24sIHZpc2l0ZWRbZW5kXSk7CglzaG9ydFBhdGhbc3RhdGlvbl1bMF1bMF0gPSBwYXRoTnVtOwoJc2hvcnRQYXRoW3N0YXRpb25dWzBdWzFdID0gdmlzaXRlZFtlbmRdOwoJZm9yKGludCBpID0gMTsgaSA8PSBwYXRoTnVtOyBpKyspewoJCXFzb3J0KCZzaG9ydFBhdGhbc3RhdGlvbl1bMV0sIHBhdGhOdW0sIHNpemVvZihpbnQpKjEwMDQsIGNtcDIpOwoJfQp9CgppbnQgbWFpbigpewoJCglpbnQgY2l0eU51bSwgbmlnaHROdW07CglzY2FuZigiJWQgJWQiLCAmY2l0eU51bSwgJm5pZ2h0TnVtKTsKCWZvcihpbnQgaSA9IDE7IGkgPD0gY2l0eU51bTsgaSsrKXsKCQlpbnQgY2l0eSwgdG1wLCBjb25uZWN0ZWQgPSAwOwoJCWNoYXIgY2g7CgkJc2NhbmYoIiVkIiwgJnRtcCk7CgkJd2hpbGUoc2NhbmYoIiVkJWMiLCAmY2l0eSwgJmNoKSAhPSBFT0YpewogICAgCQljaXR5RWRnZVt0bXBdWysrY29ubmVjdGVkXSA9IGNpdHk7CgkJCWlmKGNoID09ICdcbicpIGJyZWFrOwoJCX0KCQljaXR5RWRnZVt0bXBdWzBdID0gY29ubmVjdGVkOwoJCXFzb3J0KGNpdHlFZGdlW3RtcF0gKyAxLCBjb25uZWN0ZWQsIHNpemVvZihpbnQpLCBjbXApOwoJfQoJCglmb3IoaW50IGkgPSAxOyBpIDw9IG5pZ2h0TnVtOyBpKyspewoJCW1lbXNldChzaG9ydFBhdGgsIDAsIHNpemVvZihpbnQpICogMTAgKiA1MDAgKiAxMDA0KTsKCQlwcmludGYoIk5pZ2h0ICVkOlxuIiwgaSk7CgkJaW50IGNpdHlDb25uZWN0ZWRbMTBdOwoJCWludCBjaXR5LCBjb25uZWN0ZWQgPSAwOwoJCWNoYXIgY2g7CgkJd2hpbGUoc2NhbmYoIiVkJWMiLCAmY2l0eSwgJmNoKSAhPSBFT0YpewogICAgCQljaXR5Q29ubmVjdGVkWysrY29ubmVjdGVkXSA9IGNpdHk7CgkJCWlmKGNoID09ICdcbicpIGJyZWFrOwoJCX0KCQkKCQlmb3IoaW50IGkgPSAxOyBpIDwgY29ubmVjdGVkOyBpKyspewoJCQkvL3ByaW50ZigiJWQgJWQ6XG4iLCBjaXR5Q29ubmVjdGVkW2ldLCBjaXR5Q29ubmVjdGVkW2krMV0pOwoJCQlCRlMoY2l0eUNvbm5lY3RlZFtpXSwgY2l0eUNvbm5lY3RlZFtpKzFdLCBpLTEpOwoJCX0KCQkKCQlpbnQgbGVuID0gMDsKCQlpbnQgcGF0aCA9IDE7CgkJCgkJZm9yKGludCBpID0gMTsgaSA8IGNvbm5lY3RlZDsgaSsrKXsKCQkJcGF0aCAqPSBzaG9ydFBhdGhbaS0xXVswXVswXTsKCQkJbGVuICs9IHNob3J0UGF0aFtpLTFdWzBdWzFdOwoJCX0KCQlwcmludGYoIlBvc3NpYmxlIHdheXM6ICVkXG5OdW1iZXIgb2Ygc3RhdGlvbnM6ICVkXG4iLCBwYXRoLCBsZW4gKyAxKTsKCQlwdXRzKCJQYXRoOiIpOwoJCWNvbiA9IGNvbm5lY3RlZDsKCQllbmRzcyA9IGNpdHlDb25uZWN0ZWRbY29ubmVjdGVkXTsKCQltZW1zZXQob3V0cHV0U3RhY2ssIDAsIHNpemVvZihpbnQpICogMTAwNCk7CgkJb3V0cHV0U3RhY2tbMF0gPSBjaXR5Q29ubmVjdGVkWzFdOwoJCW91dHB1dHN0YWNrKDAsIDApOwoJCXB1dHMoIiIpOwoJfQp9