가족

괴물 가족 구성원들이 서로 얼마나 가까운 관계인지 측정하려고 합니다. 모든 괴물은 같은 수의 유전자를 가지지만, 개별 유전자는 괴물마다 다를 수 있습니다. 두 괴물이 유전자를 몇 개나 공유하는지 알 수 있다면 좋겠지만, 유전자 수가 매우 많아 직접 세는 것은 불가능합니다. 다만 우리는 가족 그래프(정확히 트리는 아닙니다)와 유전자가 유전되는 방식을 알고 있으므로, 공유 유전자 수의 기댓값을 정확히 계산할 수 있습니다.

유전 규칙은 간단합니다. 괴물 $C$가 괴물 $A$와 $B$의 자식이라면, $C$의 각 유전자는 (유전자마다 독립적으로) 확률 $50\%$로 $A$의 대응 유전자와, 확률 $50\%$로 $B$의 대응 유전자와 동일합니다. 모든 괴물의 모든 유전자는 서로 독립적으로 유전됩니다.

두 괴물 $X$와 $Y$의 관계도를 공유 유전자 수의 기댓값으로 정의합니다. 예를 들어 서로 완전히 무관한(공유 유전자가 없는) 두 괴물 $A$, $B$와 그들의 두 자식 $C$, $D$로 이루어진 가족을 생각해 봅시다. $C$의 각 유전자는 확률 $50\%$씩 $A$ 또는 $B$에서 오고, $D$도 마찬가지입니다. 따라서 $C$의 어떤 유전자가 $D$의 대응 유전자와 같을 확률은 $50\%$이며, $C$와 $D$의 관계도는 전체 유전자의 $50\%$가 됩니다. 만약 $A$와 $B$가 서로 관계가 있었다면 답은 달라집니다. $A$와 $B$가 공유하는 유전자는 $C$와 $D$ 모두에게 반드시 유전되기 때문입니다.

가족 그래프와 괴물 쌍의 목록이 주어질 때, 각 쌍의 관계도를 구하세요. 여러분의 프로그램은 다음을 수행해야 합니다.

• 표준 입력에서 가족의 정보와 구성원 쌍의 목록을 읽고,
• 각 쌍의 관계도를 백분율로 계산하여,
• 표준 출력에 결과를 씁니다.

첫 번째 줄에 공백으로 구분된 두 정수 $n$과 $k$가 주어집니다. $n$ ($2 \le n \le 300$)은 가족 구성원의 수이며, 구성원은 $1$부터 $n$까지 임의로 번호가 매겨집니다. $k$ ($0 \le k \le n-2$)는 부모가 있는 괴물의 수이고, 나머지 괴물은 모두 신이 창조하여 서로 완전히 무관합니다.

다음 $k$개의 줄에는 각각 공백으로 구분된 서로 다른 세 정수 $a$, $b$, $c$가 주어지며, 이는 괴물 $a$가 괴물 $b$와 $c$의 자식임을 의미합니다.

그다음 줄에는 정수 $m$ ($1 \le m \le n^2$), 즉 쌍의 개수가 주어집니다. 이어지는 $m$개의 줄에는 각각 두 괴물의 번호가 주어집니다.

어떤 괴물도 자기 자신의 조상이 아닙니다. 입력에 대해 그 외의 어떤 가정도 하지 마세요. 특히 유효한 성별 배정이 존재한다고 가정해서는 안 됩니다.

$m$개의 줄을 출력합니다. $i$번째 줄은 $i$번째 쌍에 대응하며, 그 쌍의 정확한 관계도를 백분율로 나타낸 값 뒤에 퍼센트 기호(%)를 붙여 출력합니다. 의미 없는 $0$은 출력하지 마세요. 다만 소수점 앞에는 반드시 한 자리 이상의 숫자가 있어야 합니다(예를 들어 $0.1$의 맨 앞 $0$은 의미가 있으므로 .1처럼 생략할 수 없습니다). 정확한 값은 항상 유한소수입니다.