그래프 여행

Ada는 마법의 나라 A에 살며 마법 대학에 다닌다. 오늘 Ada는 특별한 공간에서 마법 포인트를 모으려고 한다.

공간에는 $N$개의 방 $(0,1, \cdots ,N-1)$이 있다. 방을 잇는 $M$개의 복도가 있다. 복도 $j$는 방 $X\_j$와 방 $Y\_j$를 연결하며, 두 방 사이를 오갈 수 있다.

$i$번째 방에는 $A\_i$개의 마법 포인트가 있고, $L\_i$와 $R\_i$ 성질을 가진 마법 방패로 보호된다. $i$번째 방에 들어가려면 먼저 이미 방패가 부서진 방들만 거쳐서 $i$번째 방과 인접한(즉 복도로 연결된) 어떤 방에 도달해야 한다. 그런 다음 이 방의 방패를 부숴야 하는데, 방패는 현재 마법 포인트가 $L\_i$ 이상 $R\_i$ 이하일 때만 부술 수 있다. 방패를 부수면 방에 들어가고, 이 방에 배정된 $A\_i$개의 마법 포인트를 자동으로 얻는다. 방은 새로운 마법 포인트를 생성하지 않는다. 방패가 부서진 뒤에는 새 방패가 생기지 않으므로, 방패가 이미 부서진 모든 방은 현재 포인트와 상관없이 자유롭게 다시 갈 수 있다.

Ada는 $0$개의 마법 포인트를 가지고 시작하며, 정확히 $K$개의 마법 포인트를 모으는 방법을 찾는 것이 목표이다. 어느 방에서 시작해도 되고 어느 방에서 끝나도 된다. 시작하는 방은 방패가 자동으로 부서진 상태이고, 이 방의 마법 포인트를 모두 자동으로 얻는다.

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

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 방의 수, 복도의 수, 모으려는 마법 포인트의 수를 나타내는 세 정수 $N$, $M$, $K$가 주어진다.

다음 $N$개의 줄에는 $i$번째 방의 마법 방패 성질 $L\_i$와 $R\_i$, 마법 포인트의 수 $A\_i$를 나타내는 세 정수 $L\_i$, $R\_i$, $A\_i$가 주어진다.

다음 $M$개의 줄에는 복도 $j$가 연결하는 두 방 $X\_j$, $Y\_j$를 나타내는 두 정수가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 $K$개의 마법 포인트를 모으는 방법의 수이다.

• $1 \le T \le 100$.
• $0 \le M \le \frac{N \times (N-1)}{2}$.
• $0 \le X\_j,Y\_j \le N-1$.
• $X\_j \ne Y\_j$.
• 각 방 쌍은 많아야 하나의 복도로 연결된다.

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

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

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