초공간 항로

먼 미래, 행성 사이에서는 일방통행 무역 항로를 따라 식량이 운송된다. 각 항로는 두 행성을 직접 연결하며, 통과에 걸리는 시간이 정해져 있다.

무역 길드는 최근 발견된 초공간(hyperspace) 이동 기술을 이용해 새로운 항로를 추가하려 한다. 초공간 이동 역시 일방통행이다. 아직 실험 단계라 초공간 이동 시간은 정해지지 않았지만, 행성 사이의 거리와 무관하다는 사실은 알려져 있어 모든 초공간 항로의 통과 시간은 서로 같다. 이 공통 시간을 $x$라 하자.

아래 그림은 세 행성이 연결된 경우와 각 통과 시간을 보여 준다. 행성은 양의 정수로 번호가 매겨져 있고, 초공간 이동 시간은 $x$로 표기한다(이 그림은 두 번째 테스트 케이스의 그래프를 나타낸다).

통과 시간은 일(day) 단위로 측정되며 항상 양의 정수이고, 초공간 시간 $x$ 역시 양의 정수이다.

길드는 두 행성 $A$와 $B$에 대해, $x$가 가질 수 있는 모든 값에 걸쳐 $A$에서 $B$까지 최단 경로 총 통과 시간이 가질 수 있는 모든 값을 알고 싶어 한다. 예를 들어 위 상황에서 행성 2에서 행성 1로 가는 최단 경로는 $x \ge 5$일 때 $5$일, 그렇지 않으면($x < 5$) $4$, $3$, $2$, $1$일이 걸릴 수 있다.

첫째 줄에 행성의 수 $P$와 항로의 수 $R$가 주어진다 ($1 \le P \le 500$, $0 \le R \le 10000$).

이어지는 $R$개의 줄에는 각각 두 행성 번호 $C$, $D$ ($1 \le C, D \le P$, $C \ne D$)와 이동 시간 $T$가 주어진다. 일반 항로의 경우 $T$는 정수이고 ($1 \le T \le 10^6$), 초공간 항로의 경우 $T$는 문자 x이다. 같은 두 행성 사이에 여러 항로가 있을 수 있다.

다음 줄에는 질의의 수 $Q$가 주어진다 ($1 \le Q \le 10$).

이어지는 $Q$개의 줄에는 각각 두 행성 번호 $A$, $B$ ($A \ne B$)가 주어지며, 이는 “$A$에서 $B$까지 최단 경로 통과 시간이 가질 수 있는 값은 무엇인가?”라는 질의를 뜻한다.

질의마다 한 줄씩, 총 $Q$개의 줄을 출력한다.

각 줄에는 서로 다른 가능한 값의 개수와 그 합, 두 정수를 출력한다. 만약 서로 다른 값의 개수가 무한하다면 그 줄에는 대신 inf만 출력한다. $A$에서 $B$로 가는 경로가 없다면 서로 다른 값의 개수와 합은 모두 $0$이다(0 0을 출력한다).

첫 번째 예제에 대한 설명:

1. 행성 2에서 행성 1로 가는 경로가 없으므로 답은 0 0이다.
2. 모든 양의 정수 $x$에 대해 1에서 3까지 최단 경로는 $2x$일이 걸리므로, 값의 개수가 무한하여 답은 inf이다.
3. 1에서 4까지 최단 경로는 $x = 1$일 때 $3$일, $x = 2$일 때 $6$일, $x \ge 3$일 때 $8$일이 걸린다. 서로 다른 값은 $3$개이고 그 합은 $3 + 6 + 8 = 17$이다.