그래프 여행

Ada는 마법의 나라 A에 살며, Magic University에서 공부하고 있다. 오늘 Ada는 특별한 공간에서 마법 점수를 모으려고 한다.

이 공간에는 $\mathbf{N}$개의 방 $(0, 1, \dots, \mathbf{N}-1)$이 있다. 방들을 연결하는 복도는 $\mathbf{M}$개 있다. 복도 $j$는 방 $\mathbf{X_j}$와 방 $\mathbf{Y_j}$을 연결하며, 이는 두 방 사이를 이동할 수 있다는 뜻이다.

$i$번째 방에는 $\mathbf{A_i}$의 마법 점수가 있으며, 속성이 $\mathbf{L_i}$와 $\mathbf{R_i}$인 마법 방패로 보호되어 있다. $i$번째 방에 들어가려면 먼저 방패가 이미 부서진 방들을 거쳐 $i$번째 방에 인접한 아무 방(즉, 복도로 연결된 방)에 도달해야 한다. 그런 다음 이 방의 방패를 부숴야 하는데, 가진 마법 점수가 $\mathbf{L_i}$ 이상 $\mathbf{R_i}$ 이하일 때, 그리고 그럴 때에만 방패를 부술 수 있다. 방패를 부수면 그 방에 들어가며, 이 방에 배정된 $\mathbf{A_i}$의 마법 점수를 자동으로 모은다. 이 방에서는 새로운 마법 점수가 생성되지 않는다. 또한 방패가 부서진 뒤에는 새로운 방패가 생성되지 않으므로, 가진 점수의 양과 관계없이 방패가 이미 부서진 모든 방으로 자유롭게 돌아갈 수 있다.

Ada는 $0$의 마법 점수를 가진 채 시작하며, 정확히 $\mathbf{K}$의 마법 점수를 모을 방법을 찾는 것이 목표다. 아무 방에서나 시작할 수 있고, 아무 방에서나 끝낼 수 있다. 시작하기로 선택한 방의 마법 방패는 자동으로 부서지며, 그 방의 모든 마법 점수를 자동으로 모은다.

방과 복도의 지도를 살펴본 뒤 Ada는 이 과제가 매우 쉽다고 생각하여, 더 어려운 과제에 도전하려고 한다. 목표에 도달하는 서로 다른 방법이 몇 개인지 알고 싶어 한다. 두 방법의 고유 경로가 서로 다르면 두 방법은 다르다. 고유 경로는 방패를 부순 방들의 순서다. 예를 들어 방들을 $(1, 3, 2, 1, 3, 5, 3, 6)$ 순서로 방문하면 고유 경로는 $(1, 3, 2, 5, 6)$이다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $0 \le \mathbf{M} \le \frac{N \times (N-1)}{2}$. $\mathbf{0} \le \mathbf{X_j}, \mathbf{Y_j} \le \mathbf{N-1}$. $\mathbf{X_j} \neq \mathbf{Y_j}$ 각 방 쌍은 최대 하나의 복도로 연결될 수 있다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 8$. $1 \le \mathbf{K} \le 100$. $0 \le \mathbf{L_i} \le \mathbf{R_i} \le 50$. $1 \le \mathbf{A_i} \le 50$.

테스트 세트 2

시간 제한: 60초. $1 \le \mathbf{N} \le 15$. $1 \le \mathbf{K} \le 2 \times 10^9$. $0 \le \mathbf{L_i} \le \mathbf{R_i} \le 10^9$. $1 \le \mathbf{A_i} \le 10^9$.

입력의 첫째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 세 정수 $\mathbf{N}$, $\mathbf{M}$, $\mathbf{K}$가 주어지며, 각각 방의 수, 복도의 수, 모으려는 마법 점수의 양을 나타낸다. 다음 $\mathbf{N}$개의 줄에는 세 정수 $\mathbf{L_i}$, $\mathbf{R_i}$, $\mathbf{A_i}$가 주어지며, 각각 방 $i$의 마법 방패 속성 $\mathbf{L_i}$와 $\mathbf{R_i}$, 그리고 마법 점수의 양 $\mathbf{A_i}$을 나타낸다. 다음 $\mathbf{M}$개의 줄에는 두 정수 $\mathbf{X_j}$와 $\mathbf{Y_j}$가 주어지며, 복도 $j$로 연결된 방들을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$은 $\mathbf{K}$의 마법 점수를 모으는 방법의 수다.

첫 번째 경우에는 서로 다른 방법이 $4$개 있다. 그 방법들은 다음과 같다.

두 번째 경우에는 서로 다른 방법이 $8$개 있다. 그 방법들은 다음과 같다.

세 번째 경우에는 서로 다른 방법이 $4$개 있다. 그 방법들은 다음과 같다.