Problem J
Happy Friends

Input: Standard Input

Output: Standard Output

 

The happiness of your friends makes you happier, and this increase of your happiness also has impact on your friends' happiness. What if no other effect (like dissatisfaction, poverty, enmity etc.) exits? The happiness would always increase day by day in a friendship network.

 

Can you help to analyze the scenario if only happiness exists in a friendship network? You are given a friendship network of N friends. You can identify them by integers from 0 to N - 1. You are also given M pairs of integer. Each pair represents a friendship between two persons in that network. You are also given a person who is the first happy person in the network. The initial degree of happiness of that first person is 1. Initial degree of happiness of all others in that friendship network is 0. The network will be given in such a way that each person’s degree of happiness will be affected after a certain period by the initial happy person.

 

Can you answer, what will be the degree of happiness of all of N persons in that network after D days if the degree of happiness of each person increases by a defined rule?

The only simple rule is - Each day, a person's degree of happiness is increased if and only if his degree of happiness is not increased in previous day. If the degree of happiness is not increased in previous day then it will increased by the summation of degree of happiness of all of his friends at previous day.

 

To make it more clear, let us consider a person p, and his degree of happiness is not increased at dth day, so his degree of happiness will increase at (d+1)th day by the summation of degree of happiness of all of his friends at dth day. But if his degree of happiness increased at dth day, it will remain same after (d+1)th day.

 

Input

Input will start with an integer T(1 ≤ T ≤ 200), number of test cases. Each case starts with four integers N(1 ≤ N ≤ 30), M(N-1 ≤ M ≤ N*(N-1)/2), K(0 ≤ K ≤ N-1) and D(0 ≤ D ≤ 1000000000), number of nodes, number of friendships, initial happy person and number of days. Each of the next M lines will contain two integers u and v(0 ≤ u, v ≤ N-1, u≠v), which represents that u and v are friends.

 

Output

For each test case output a single line providing the case number followed by N space separated integers. The ith integer represents the degree of happiness of ith person after D days.  The degree of happiness can be very large so that you should output the value of degree of happiness modulo 1000000007.

 

See sample input and output for exact format.

 

Sample Input                          Output for Sample Input

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

 

Case 1: 1 0
Case 2: 2 4 1 1

 

Problem setter: Arifuzzaman Arif

Special Thanks: Manzurur Rahman Khan