시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 16 1 1 16.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+XHJcblxyXG48cD5cdWM1YjRcdWIyOTBcdWIwYTAgeXVtM1x1Yzc0MCBcdWIzYzRcdWMyZGMgc1x1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWM1ZWMgXHViM2M0XHVjMmRjIHRcdWI4NWMgXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YjVhMFx1YjA5OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWMxMzhcdWFjYzRcdWM3NTggXHViM2M0XHVjMmRjXHVjNjQwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWQ1NThcdWIwOTggXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWIzYzRcdWMyZGMgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWUzOFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWMyMThcdWIyOTQgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHViM2M0XHVjYzI5XHVjODEwXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWFlMzhcdWM3NDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD55dW0zXHVjNzQwIFx1YjNjNFx1YzJkYyB0XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWI1NGNcdWFlNGNcdWM5YzBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVhZTM4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWMgXHVhZGUwXHViNGYxXHVkNTVjIFx1ZDY1NVx1Yjk2MFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWJhNzAsIFx1YWMxOVx1Yzc0MCBcdWIzYzRcdWMyZGNcdWIwOTggXHVhZTM4XHVjNzQ0IFx1YzVlY1x1YjdlYyBcdWJjODggXHVjOWMwXHViMDk4XHViM2M0IFx1YzBjMVx1YWQwMFx1YzVjNlx1YjJlNC4gXHViMmU4LCBcdWIzYzRcdWMyZGMgdFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWFjNzBcdWIwOTggXHViM2M0XHVjMmRjIHRcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjNWI0XHViNWE0IFx1YjNjNFx1YzJkY1x1YzVkMCBcdWM3NzRcdWI5NzRcdWFjOGMgXHViNDE4XHViYTc0IFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWM5ODlcdWMyZGMgXHViYTQ4XHVjZDk4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgdFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWM3M2NcdWJhNzRcdWMxMWMgXHVjZDljXHViYzFjXHVjOWMwXHViZDgwXHVkMTMwIFx1YzljMFx1YjA5OFx1YzYyOCBcdWFlMzhcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMzU4IFx1YWUwMFx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHVjNWY0XHVkNTU4XHVjNWVjLCBcdWI5Y2NcdWM1N2QgXHVhZGY4XHVhYzgzXHVjNzc0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YmE3NCBsdWNreVx1ZDU1OFx1YjJlNFx1YWNlMCBcdWIyOTBcdWIwODBcdWIyZTQuIFx1YjljY1x1YzU3ZCB0XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1YjQxOFx1YWM3MFx1YjA5OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgbHVja3lcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD55dW0zXHVjNzc0IGx1Y2t5XHVkNTVjIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWQ2NTVcdWI5NjBcdWM3NDAgXHVjNWJjXHViOWM4XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKCZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzExYyBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmU0OCBcdWM5MDRcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVhY2UwLCBcdWM3NzRcdWM1YjRcdWMxMWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVhYzFjXHVjMjE4IG4sIFx1YWUzOFx1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQoMiAmbGU7IG4gJmxlOyAxMiwgMCAmbGU7IG0gJmxlOzEwMDApLiBcdWM3NzRcdWM1YjRcdWMxMWMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1YWUzOFx1Yzc1OCBcdWM4MTVcdWJjZjQgXHVjODE1XHVjMjE4IHUsIHYoMCAmbGU7IHUsIHYgJmx0OyBuLCB1ICZuZTsgdiksIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTAgd1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IFx1YjNjNFx1YzJkYyB1XHVjNWQwXHVjMTFjIFx1YjNjNFx1YzJkYyB2XHViODVjIFx1YWMwMFx1YjI5NCBcdWM3N2NcdWJjMjlcdWQ1YTUgXHVhZTM4XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3MCBcdWFkZjggXHVhZTM4XHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWFlMDBcdWM3OTBcdWFjMDAgd1x1Yjc3Y1x1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzExYyBcdWQ1NThcdWIwOThcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzljOFx1YmIzOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YzgxNVx1YzIxOCBxKCZsZTsgMTUwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1Yzc3NFx1YzViNFx1YzExYyBxXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM5YzhcdWJiMzggcywgdCgwICZsZTsgcywgdCAmbHQ7IG4sIHMgJm5lOyB0KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IFx1Y2Q5Y1x1YmMxY1x1YzljMFx1YWMwMCBcdWIzYzRcdWMyZGMgcywgXHViM2M0XHVjYzI5XHVjOWMwXHVhYzAwIFx1YjNjNFx1YzJkYyB0XHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1YzJkZFx1YzVkMCBcdWI5ZGVcdWFjOGMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWM3NzRcdWM1YjRcdWMxMWMgXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBcdWM5YzhcdWJiMzhcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWFjMTJcdWM3NDAgXHVjODE1XHViMmY1XHVhY2ZjIDEwPHN1cD4tNDxcL3N1cD4gXHViYmY4XHViOWNjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YWMwMCBcdWIwOThcdWJhNzQgXHVjODE1XHViMmY1XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NjIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJhdmVsaW5nIEZvb2wiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBtdXN0IGhhdmUgaGVhcmQgdGhlICZsc3F1bztUcmF2ZWxpbmcgU2FsZXNtYW4gUHJvYmxlbSZyc3F1bzsuIEhlcmUgd2UgYXJlIHRhbGtpbmcgYWJvdXQgYW5vdGhlciBwcm9ibGVtIG5hbWVkICZsc3F1bztUcmF2ZWxpbmcgRm9vbCBQcm9ibGVtJnJzcXVvOy4gQXNzdW1lIHRoYXQgdGhlcmUgYXJlIG4gY2l0aWVzIGNvbm5lY3RlZCBieSBtIG9uZSB3YXkgcm9hZHMuIEVhY2ggcm9hZCBpcyBsYWJlbGVkIGJ5IGFuIHVwcGVyY2FzZSBFbmdsaXNoIGxldHRlciAoaS5lICZsc3F1bztBJnJzcXVvOyB0byAmbHNxdW87WiZyc3F1bzspLiBUaGVyZSBjYW4gYmUgbXVsdGlwbGUgcm9hZHMgYmV0d2VlbiB0d28gY2l0aWVzIGJ1dCBubyByb2FkcyB3aWxsIHN0YXJ0IGFuZCBlbmQgYXQgdGhlIHNhbWUgY2l0eS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRyYXZlbGluZyBmb29sIHN0YXJ0cyBoaXMgam91cm5leSBmcm9tIGNpdHkgcyBhbmQgaGUgY29udGludWVzIGhpcyBqb3VybmV5IHVudGlsIGhlIHJlYWNoZXMgdCwgb3IgaGUgcmVhY2hlcyBhIGNpdHkgZnJvbSB3aGljaCB0IGlzIHVucmVhY2hhYmxlLiBJZiBoZSBpcyBpbiBjaXR5IHUsIGhlIGNhbiBjaG9vc2UgYW55IHJvYWQgdGhhdCBzdGFydHMgZnJvbSB1IHdpdGggZXF1YWwgcHJvYmFiaWxpdHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlIG1heSB2aXNpdCBzYW1lIGNpdHlcL3JvYWQgbW9yZSB0aGFuIG9uY2UsIGJ1dCBvbmNlIGhlIHJlYWNoZXMgdCwgaGUgaW1tZWRpYXRlbHkgc3RvcHMgaGlzIGpvdXJuZXkgYW5kIHJlbWVtYmVycyB0aGUgcm9hZC1sYWJlbHMgaGUgZm91bmQgaW4gaGlzIHBhdGggaW4gdGhlIHNhbWUgb3JkZXIgdGhlIHJvYWRzIHdlcmUgdmlzaXRlZC4gSWYgdGhlIHJvYWQtbGFiZWxzIGluIHRoZSBwYXRoIGhlIHRyYXZlbGVkIGZvcm0gYSBwYWxpbmRyb21lLCBoZSBmaW5kcyBoaW1zZWxmIGx1Y2t5LiBJZiBoZSBpcyB1bmFibGUgdG8gcmVhY2ggdCBvciB0aGUgcm9hZC1sYWJlbHMgZG9uJnJzcXVvO3QgZm9ybSBhIHZhbGlkIHBhbGluZHJvbWUsIGhlIGZpbmRzIGhpbXNlbGYgdW5sdWNreS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGNpdGllcywgcm9hZHMsIHMgYW5kIHQsIGNhbiB5b3UgZmluZCB0aGUgcHJvYmFiaWxpdHkgb2YgTXIgVHJhdmVsaW5nIEZvb2wgYmVpbmcgbHVja3k/Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIFQgKCZsZTsgMTAwKSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGNhc2Ugc3RhcnRzIHdpdGggYSBibGFuayBsaW5lLiBOZXh0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIG4gKDIgJmxlOyBuICZsZTsgMTIpIGFuZCBtICgwICZsZTsgbSAmbGU7MTAwMCkuIEVhY2ggb2YgdGhlIG5leHQgbSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMsIHUgdiAoMCAmbGU7IHUsIHYgJmx0OyBuLCB1ICZuZTsgdikgYW5kIGFuIHVwcGVyY2FzZSBFbmdsaXNoIGxldHRlciB3LCBtZWFuaW5nIHRoYXQgdGhlcmUgaXMgYSBvbmUtd2F5IHJvYWQgZnJvbSBjaXR5IHUgdG8gY2l0eSB2IGFuZCB0aGUgcm9hZCBsYWJlbCBpcyB3LiBOZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAoMSAmbGU7IHEgJmxlOyAxNTApIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgcXVlcmllcy4gRWFjaCBvZiB0aGUgbmV4dCBxIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBkZW5vdGluZyBzIHQgKDAgJmxlOyBzLCB0ICZsdDsgbiwgcyAmbmU7IHQpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIHByaW50IHRoZSBjYXNlIG51bWJlciBmaXJzdC4gVGhlbiBmb3IgZWFjaCBxdWVyeSwgcHJpbnQgdGhlIHByb2JhYmlsaXR5IGFzIHN0YXRlZC4gRXJyb3JzIGxlc3MgdGhhbiAxMDxzdXA+LTQ8XC9zdXA+IHdpbGwgYmUgaWdub3JlZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=