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 hasrooms . There are corridors connecting the rooms. A corridor connects room and room , meaning you can travel between the two rooms.
The-th room contains magic points and is protected by a magic shield with properties and . To enter the -th room, first you need to get to any room adjacent to the -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 and magic points, inclusive. After you break the shield, you will enter the room and automatically collect the 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 withmagic points and her goal is to find a way to collect exactly 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, the unique path is .
The first line of the input gives the number of test cases,
For each test case, the first line contains three integers , , and : the number of rooms, the numbers of corridors, and the numbers of magic points we want to collect, respectively.
The next lines contain three integers , , and : The magic shield properties and of room , and the number of magic points , respectively.
The next lines contain two integers and : the rooms that are connected by corridor .
For each test case, output one line containing
Case #, where : is the test case number (starting from 1) and is the number of ways to collect magic points.
Memory limit: 1 GB.
Each pair of rooms can be connected by at most one corridor.
Test Set 1
Time limit: 20 seconds.
Test Set 2
Time limit: 60 seconds.
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 aredifferent ways. They are:
In the second case, there aredifferent ways. They are:
In the third case, there aredifferent ways. They are: