Since all of aslı's friends left her, she is trying to find new friends. To accomplish this aslı is going to meet with the friends of yiit, only person left she can trust.

After being friends with yiit's friend, aslı can meet with him/her friends in the following days. But she has a problem. Because she's a little shy, she can't meet more than \(K\) people in a day.

Can you find how many friends aslı will have in the end of \(G\)'th day?

Input

The first line will include 4 numbers. Those are:

• \(\mathbf{N}\) indicating total number of people.
• \(\mathbf{M}\) indicating total number of friendships.
• \(\mathbf{K}\) indicating how many people aslı can meet in a day.
• \(\mathbf{G}\) indicating total number of days.

The next \(\mathbf{M}\) indicates friendships. In each line the pair of \(\mathbf{A_i}\) and \(\mathbf{B_i}\) indicate that \(\mathbf{A_i}\) and \(\mathbf{B_i}\) are friends. \(\mathbf({A_i \ne B_i)}\)

Batch #1:

• \(1 \leq \mathbf{N} \leq 100\)
• \(1 \leq \mathbf{M} \leq 300\)
• \(1 \leq \mathbf{K, G} \leq 20\)
• \(1 \leq \mathbf{len(A_i), len(B_i)} \leq 8\)

Batch #2:

• \(1 \leq \mathbf{N} \leq 10^4\)
• \(1 \leq \mathbf{M} \leq 3 \cdot 10^4\)
• \(1 \leq \mathbf{K, G} \leq 20\)
• \(1 \leq \mathbf{len(A_i), len(B_i)} \leq 8\)

Output

Print only how many friends aslı will have in the of \(G\) days.

Samples

Input:

5 5 2 2
yiit cartman
yiit butters
butters jimmy
stan jimmy
jimmy yiit

Output:

4

Input:

7 8 3 3
yiit hankey
garrison slave
santa kyle
hankey kyle
garrison rat
slave rat
rat santa
santa hankey

Output:

4