시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB171116.667%

문제

최흉최악의 해커 yum3은 팰린드롬에 집착하는 경향이 있다(정작 자신의 이름은 팰린드롬이 아니다).

어느 날 yum3은 도시 s에서 출발하여 도시 t로 여행을 떠나게 되었다. 이 세계의 도시와 도시 사이에 있는 모든 길에는 알파벳 대문자가 하나 적혀 있다. 같은 두 도시 사이에 길이 여러 개 존재할 수는 있지만, 시작점과 도착점이 같은 길은 없다.

yum3은 도시 t에 도착할 때까지는 현재 도시에서 인접한 길 중 하나로 균등한 확률로 이동하며, 같은 도시나 길을 여러 번 지나도 상관없다. 단, 도시 t에 도착하거나 도시 t로 갈 수 없는 어떤 도시에 이르게 되면 여행을 즉시 멈춘다. 그리고 t에 도착했으면서 출발지부터 지나온 길에 적혀있던 글자들을 순서대로 나열하여, 만약 그것이 팰린드롬이면 lucky하다고 느낀다. 만약 t에 도착할 수 없게 되거나 경로가 팰린드롬을 이루지 않으면 lucky하지 못하다.

yum3이 lucky한 여행을 할 수 있을 확률은 얼마일까?

입력

첫째 줄에 테스트 케이스의 개수 T(≤ 100)가 주어진다. 이어서 각 테스트 케이스가 여러 줄에 걸쳐 주어진다.

각 테스트 케이스는 빈 줄로 시작하고, 이어서 한 줄에 도시의 개수 n, 길의 개수 m이 주어진다(2 ≤ n ≤ 12, 0 ≤ m ≤1000). 이어서 m개의 줄에 각 길의 정보 정수 u, v(0 ≤ u, v < n, u ≠ v), 알파벳 대문자 w가 주어지는데 이는 도시 u에서 도시 v로 가는 일방향 길이 존재하며 그 길에 적힌 글자가 w라는 의미이다. 이어서 하나의 줄에 질문의 개수를 의미하는 정수 q(≤ 150)가 주어지고, 이어서 q개의 줄에 질문 s, t(0 ≤ s, t < n, s ≠ t)가 주어지는데 이는 출발지가 도시 s, 도착지가 도시 t라는 의미이다.

출력

각 테스트 케이스마다 첫째 줄에 양식에 맞게 테스트 케이스 번호를 출력하고, 이어서 각 줄마다 질문에 대한 답을 출력한다. 각 값은 정답과 10-4 미만의 오차가 나면 정답으로 인정된다.

예제 입력 1

2

4 3
0 1 A
1 2 A
2 3 A
2
0 3
2 0


5 4
1 2 B
2 3 D
2 4 A
2 0 B
2
1 3
1 0

예제 출력 1

Case 1:
1.000000
0.000000
Case 2:
0.000000
0.333333
W3sicHJvYmxlbV9pZCI6Ijk2MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHVjNWVjXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkNWNcdWQ3NDlcdWNkNWNcdWM1NDVcdWM3NTggXHVkNTc0XHVjZWU0IHl1bTNcdWM3NDAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNWQwIFx1YzlkMVx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWQ1YTVcdWM3NzQgXHVjNzg4XHViMmU0KFx1YzgxNVx1Yzc5MSBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQpLjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHViMGEwIHl1bTNcdWM3NDAgXHViM2M0XHVjMmRjIHNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1YjNjNFx1YzJkYyB0XHViODVjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI1YTBcdWIwOThcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWM3NzQgXHVjMTM4XHVhY2M0XHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCBcdWIzYzRcdWMyZGMgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhZTM4XHVjNWQwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4IFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFlMzhcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjNjNFx1Y2MyOVx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+eXVtM1x1Yzc0MCBcdWIzYzRcdWMyZGMgdFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YWUzOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1YWRlMFx1YjRmMVx1ZDU1YyBcdWQ2NTVcdWI5NjBcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTcwLCBcdWFjMTlcdWM3NDAgXHViM2M0XHVjMmRjXHViMDk4IFx1YWUzOFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzljMFx1YjA5OFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuIFx1YjJlOCwgXHViM2M0XHVjMmRjIHRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVhYzcwXHViMDk4IFx1YjNjNFx1YzJkYyB0XHViODVjIFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YzViNFx1YjVhNCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHVjNzc0XHViOTc0XHVhYzhjIFx1YjQxOFx1YmE3NCBcdWM1ZWNcdWQ1ODlcdWM3NDQgXHVjOTg5XHVjMmRjIFx1YmE0OFx1Y2Q5OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIHRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTg4XHVjNzNjXHViYTc0XHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1YzljMFx1YmQ4MFx1ZDEzMCBcdWM5YzBcdWIwOThcdWM2MjggXHVhZTM4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjM1OCBcdWFlMDBcdWM3OTBcdWI0ZTRcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjA5OFx1YzVmNFx1ZDU1OFx1YzVlYywgXHViOWNjXHVjNTdkIFx1YWRmOFx1YWM4M1x1Yzc3NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWJhNzQgbHVja3lcdWQ1NThcdWIyZTRcdWFjZTAgXHViMjkwXHViMDgwXHViMmU0LiBcdWI5Y2NcdWM1N2QgdFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWM4YyBcdWI0MThcdWFjNzBcdWIwOTggXHVhY2JkXHViODVjXHVhYzAwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0NCBcdWM3NzRcdWI4ZThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IGx1Y2t5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+eXVtM1x1Yzc3NCBsdWNreVx1ZDU1YyBcdWM1ZWNcdWQ1ODlcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVkNjU1XHViOTYwXHVjNzQwIFx1YzViY1x1YjljOFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjNWVjXHViN2VjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWJlNDggXHVjOTA0XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCwgXHVjNzc0XHVjNWI0XHVjMTFjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1YWMxY1x1YzIxOCBuLCBcdWFlMzhcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KDIgJmxlOyBuICZsZTsgMTIsIDAgJmxlOyBtICZsZTsxMDAwKS4gXHVjNzc0XHVjNWI0XHVjMTFjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWFlMzhcdWM3NTggXHVjODE1XHViY2Y0IFx1YzgxNVx1YzIxOCB1LCB2KDAgJmxlOyB1LCB2ICZsdDsgbiwgdSAmbmU7IHYpLCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwIHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1Yzc3NFx1YjI5NCBcdWIzYzRcdWMyZGMgdVx1YzVkMFx1YzExYyBcdWIzYzRcdWMyZGMgdlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjNzdjXHViYzI5XHVkNWE1IFx1YWUzOFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzAgXHVhZGY4IFx1YWUzOFx1YzVkMCBcdWM4MDFcdWQ3OGMgXHVhZTAwXHVjNzkwXHVhYzAwIHdcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM5YzhcdWJiMzhcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggcSgmbGU7IDE1MClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWM3NzRcdWM1YjRcdWMxMWMgcVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjOWM4XHViYjM4IHMsIHQoMCAmbGU7IHMsIHQgJmx0OyBuLCBzICZuZTsgdClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwIFx1Yzc3NFx1YjI5NCBcdWNkOWNcdWJjMWNcdWM5YzBcdWFjMDAgXHViM2M0XHVjMmRjIHMsIFx1YjNjNFx1Y2MyOVx1YzljMFx1YWMwMCBcdWIzYzRcdWMyZGMgdFx1Yjc3Y1x1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1OTFcdWMyZGRcdWM1ZDAgXHViOWRlXHVhYzhjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNzc0XHVjNWI0XHVjMTFjIFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjOWM4XHViYjM4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVhYzEyXHVjNzQwIFx1YzgxNVx1YjJmNVx1YWNmYyAxMDxzdXA+LTQ8XC9zdXA+IFx1YmJmOFx1YjljY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWFjMDAgXHViMDk4XHViYTc0IFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTVcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTYyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyYXZlbGluZyBGb29sIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgbXVzdCBoYXZlIGhlYXJkIHRoZSAmbHNxdW87VHJhdmVsaW5nIFNhbGVzbWFuIFByb2JsZW0mcnNxdW87LiBIZXJlIHdlIGFyZSB0YWxraW5nIGFib3V0IGFub3RoZXIgcHJvYmxlbSBuYW1lZCAmbHNxdW87VHJhdmVsaW5nIEZvb2wgUHJvYmxlbSZyc3F1bzsuIEFzc3VtZSB0aGF0IHRoZXJlIGFyZSBuIGNpdGllcyBjb25uZWN0ZWQgYnkgbSBvbmUgd2F5IHJvYWRzLiBFYWNoIHJvYWQgaXMgbGFiZWxlZCBieSBhbiB1cHBlcmNhc2UgRW5nbGlzaCBsZXR0ZXIgKGkuZSAmbHNxdW87QSZyc3F1bzsgdG8gJmxzcXVvO1omcnNxdW87KS4gVGhlcmUgY2FuIGJlIG11bHRpcGxlIHJvYWRzIGJldHdlZW4gdHdvIGNpdGllcyBidXQgbm8gcm9hZHMgd2lsbCBzdGFydCBhbmQgZW5kIGF0IHRoZSBzYW1lIGNpdHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0cmF2ZWxpbmcgZm9vbCBzdGFydHMgaGlzIGpvdXJuZXkgZnJvbSBjaXR5IHMgYW5kIGhlIGNvbnRpbnVlcyBoaXMgam91cm5leSB1bnRpbCBoZSByZWFjaGVzIHQsIG9yIGhlIHJlYWNoZXMgYSBjaXR5IGZyb20gd2hpY2ggdCBpcyB1bnJlYWNoYWJsZS4gSWYgaGUgaXMgaW4gY2l0eSB1LCBoZSBjYW4gY2hvb3NlIGFueSByb2FkIHRoYXQgc3RhcnRzIGZyb20gdSB3aXRoIGVxdWFsIHByb2JhYmlsaXR5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZSBtYXkgdmlzaXQgc2FtZSBjaXR5XC9yb2FkIG1vcmUgdGhhbiBvbmNlLCBidXQgb25jZSBoZSByZWFjaGVzIHQsIGhlIGltbWVkaWF0ZWx5IHN0b3BzIGhpcyBqb3VybmV5IGFuZCByZW1lbWJlcnMgdGhlIHJvYWQtbGFiZWxzIGhlIGZvdW5kIGluIGhpcyBwYXRoIGluIHRoZSBzYW1lIG9yZGVyIHRoZSByb2FkcyB3ZXJlIHZpc2l0ZWQuIElmIHRoZSByb2FkLWxhYmVscyBpbiB0aGUgcGF0aCBoZSB0cmF2ZWxlZCBmb3JtIGEgcGFsaW5kcm9tZSwgaGUgZmluZHMgaGltc2VsZiBsdWNreS4gSWYgaGUgaXMgdW5hYmxlIHRvIHJlYWNoIHQgb3IgdGhlIHJvYWQtbGFiZWxzIGRvbiZyc3F1bzt0IGZvcm0gYSB2YWxpZCBwYWxpbmRyb21lLCBoZSBmaW5kcyBoaW1zZWxmIHVubHVja3kuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBjaXRpZXMsIHJvYWRzLCBzIGFuZCB0LCBjYW4geW91IGZpbmQgdGhlIHByb2JhYmlsaXR5IG9mIE1yIFRyYXZlbGluZyBGb29sIGJlaW5nIGx1Y2t5PyZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgc3RhcnRzIHdpdGggYW4gaW50ZWdlciBUICgmbGU7IDEwMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBjYXNlIHN0YXJ0cyB3aXRoIGEgYmxhbmsgbGluZS4gTmV4dCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuICgyICZsZTsgbiAmbGU7IDEyKSBhbmQgbSAoMCAmbGU7IG0gJmxlOzEwMDApLiBFYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzLCB1IHYgKDAgJmxlOyB1LCB2ICZsdDsgbiwgdSAmbmU7IHYpIGFuZCBhbiB1cHBlcmNhc2UgRW5nbGlzaCBsZXR0ZXIgdywgbWVhbmluZyB0aGF0IHRoZXJlIGlzIGEgb25lLXdheSByb2FkIGZyb20gY2l0eSB1IHRvIGNpdHkgdiBhbmQgdGhlIHJvYWQgbGFiZWwgaXMgdy4gTmV4dCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgKDEgJmxlOyBxICZsZTsgMTUwKSBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMuIEVhY2ggb2YgdGhlIG5leHQgcSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgZGVub3RpbmcgcyB0ICgwICZsZTsgcywgdCAmbHQ7IG4sIHMgJm5lOyB0KS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBwcmludCB0aGUgY2FzZSBudW1iZXIgZmlyc3QuIFRoZW4gZm9yIGVhY2ggcXVlcnksIHByaW50IHRoZSBwcm9iYWJpbGl0eSBhcyBzdGF0ZWQuIEVycm9ycyBsZXNzIHRoYW4gMTA8c3VwPi00PFwvc3VwPiB3aWxsIGJlIGlnbm9yZWQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==