물물교환의 달인 Jack

Jack은 물물교환을 좋아한다. 이득을 볼 수만 있다면 무엇이든 다른 것과 바꾼다. 지금 Jack은 어떤 물건을 얻으려 하고, 그 대가로 다른 물건을 내놓을 생각이다. 필요하다면 친구들과 여러 번 교환하는 사슬(연쇄 거래)을 거쳐도 된다.

각 친구는 한 방향으로만 성립하는 거래를 제안한다. 즉, 어떤 친구가 name1 $a_1$개를 주고 name2 $a_2$개를 받는 거래를 제안하더라도, 그 반대 방향의 거래(즉 name2를 주고 name1을 받는 거래)까지 해 준다는 뜻은 아니다.

일이 너무 복잡해지지 않도록, Jack은 하나의 연쇄 거래에 자기 이외의 사람을 최대 $9$명까지만 끼워 넣는다. 즉, 한 사슬은 최대 $9$번의 거래로 이루어진다.

한 사슬의 교환 비율이란, Jack이 원하는 물건 $1$개를 얻기 위해 내놓아야 하는, 그가 내줄 물건의 개수를 뜻한다. Jack이 내줄 물건을 그가 원하는 물건으로 바꾸는 모든 사슬 중에서 가장 좋은(가장 작은) 교환 비율을 구하고, 정확히 그 비율을 달성하는 서로 다른 사슬이 몇 개인지 구하여라.

첫째 줄에 테스트 케이스의 수 $n$이 주어진다.

각 테스트 케이스의 첫째 줄에는 두 물건의 이름과 양의 정수 $m$($m \le 50$)이 주어진다. 첫 번째 이름은 Jack이 원하는 물건, 두 번째 이름은 Jack이 내줄 물건이며, $m$은 가능한 거래의 수이다. 이어지는 $m$개의 줄은 각각 다음과 같은 형식이다.

a1 name1 a2 name2

이는 어떤 친구가 물건 name1 $a_1$개를 주고 물건 name2 $a_2$개를 받을 의향이 있다는 뜻이다(친구가 name1을 주고 name2를 받는다. 단, 이 거래가 있다고 해서 반대 방향 거래까지 가능하다는 뜻은 아니다). 각 $a_1$과 $a_2$는 $20$ 이하의 양의 정수이다. 어떤 거래도 성사시키는 데 $2^{31}-1$개보다 많은 물건이 필요하지는 않다.

각 테스트 케이스마다 Case i:(여기서 $i$는 $1$부터 시작하는 테스트 케이스 번호)를 출력하고, 이어서 공백 하나, Jack이 얻을 수 있는 가장 좋은(가장 작은) 교환 비율, 다시 공백 하나, 그리고 그 비율을 얻을 수 있는 서로 다른 방법의 수를 출력한다.

교환 비율은 지수 표기가 아니라 일반적인 십진 소수(고정소수점) 표기로 나타내며, 유효숫자 $5$자리가 되도록 반올림하고 끝자리의 $0$도 그대로 표시한다. 예를 들어 1.8000, 0.28571과 같이 출력한다. 값이 두 유효숫자 $5$자리 결과의 정확히 중간에 놓이는 경우에는 올림한다.