Know More!

# Graph Travel solution kickstart – Ada lives in a magic country A, and she is studying at Magic University. Today, Ada wants to collect magic points in a special space. The space has NN rooms (0,1,…,N−1)(0,1,…,N−1). There are MM corridors connecting the rooms. A corridor jj connects room XjXj and room YjYj, meaning you can travel between the two rooms

Posted by: insureinsurancelife - Posted on:

### Problem

Ada lives in a magic country A, and she is studying at Magic University. Today, Ada wants to collect magic points in a special space.

The space has NN rooms (0,1,,N1)(0,1,…,N−1). There are MM corridors connecting the rooms. A corridor jj connects room XjXj and room YjYj, meaning you can travel between the two rooms.

The ii-th room contains AiAi magic points and is protected by a magic shield with properties LiLi and RiRi. To enter the ii-th room, first you need to get to any room adjacent to the ii-th room (i.e. connected to it by a corridor) through rooms with already broken shields. Then you have to break the shield to this room, but you can break the shield if and only if you have between LiLi and RiRi magic points, inclusive. After you break the shield, you will enter the room and automatically collect the AiAi magic points assigned to this room. The room will not generate new magic points. The room will also not generate a new shield after it is broken, so you can freely go back to every room with already broken shields regardless of the amount of points you have.

Ada starts with 00 magic points and her goal is to find a way to collect exactly KK magic points. She can start in any room, and end in any room. The room she chooses to start in will automatically have its magic shield broken, and she will automatically collect all the magic points from this room.

After inspecting the map of the rooms and corridors, Ada thinks the task is very easy, so she wants to challenge herself with a more difficult task. She wants to know how many unique ways there are to reach the goal. Two ways are different if their unique paths are different. The unique path is the order of rooms in which she broke the shields, e.g.: if you visit the rooms in the order (1,3,2,1,3,5,3,6)(1,3,2,1,3,5,3,6), the unique path is (1,3,2,5,6)(1,3,2,5,6).

### Input

The first line of the input gives the number of test cases, TTTT test cases follow.
For each test case, the first line contains three integers NNMM, and KK: the number of rooms, the numbers of corridors, and the numbers of magic points we want to collect, respectively.
The next NN lines contain three integers LiLiRiRi, and AiAi: The magic shield properties LiLi and RiRi of room ii, and the number of magic points AiAi, respectively.
The next MM lines contain two integers XjXj and YjYj: the rooms that are connected by corridor jj.

### Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the number of ways to collect KK magic points.

### Limits

Memory limit: 1 GB.
1T1001≤T≤100.
0MN×(N1)20≤M≤N×(N−1)2.
0Xj,YjN10≤Xj,Yj≤N−1.
XjYjXj≠Yj
Each pair of rooms can be connected by at most one corridor.

#### Test Set 1

Time limit: 20 seconds.
1N81≤N≤8.
1K1001≤K≤100.
0LiRi500≤Li≤Ri≤50.
1Ai501≤Ai≤50.

#### Test Set 2

Time limit: 60 seconds.
1N151≤N≤15.
1K2×1091≤K≤2×109.
0LiRi1090≤Li≤Ri≤109.
1Ai1091≤Ai≤109.

### Sample

3
4 3 3
1 3 1
1 1 1
2 4 1
2 3 1
0 1
1 2
2 3
4 5 3
1 3 1
1 1 1
2 4 1
2 3 1
0 1
1 2
2 3
3 0
0 2
4 1 2
0 4 1
0 4 1
0 4 2
0 4 2
0 1

Case #1: 4
Case #2: 8
Case #3: 4


In the first case, there are 44 different ways. They are:

In the second case, there are 88 different ways. They are:

In the third case, there are 44 different ways. They are: