Background

History falls into the hands of the winners
At least we have legends
Who says the defeated cannot be immortal
Fists can only make people bow their heads
Thoughts can make people lift their heads
Lift your head to see, to love, to chase
The dream in your heart

Problem Description

April comes to mind again.

If it weren't for the provincial competition, everyone probably wouldn't have split up so easily, right? One by one, former teammates leave the computer room.

"Do not speak of the marquis's affairs, for a general's success is built on countless bones."

In a dream, Xiao F becomes a messenger delivering secret letters to the general.

Now, two secret letters concerning the fate of the nation need to be delivered to the frontline general's tent. The journey is perilous and time is pressing. Xiao F, disregarding his own safety, bravely takes on this task.

However, Xiao F is too careless, and he accidentally loses one of the two secret letters.

Xiao F secretly opens the remaining letter. He finds a very detailed map, along with a few annotations—it turns out to be an intelligence map of the battlefield surroundings. After careful examination, he discovers that this map marks n relay stations numbered from 1 to n, connected by n-1 paths of 1 li each, with each path connecting two different relay stations bidirectionally, and all relay stations are reachable from one another.

Xiao F carefully reads the annotations and suddenly understands the content of the lost letter. It turns out that each relay station can be garrisoned by a squad, and each squad can control relay stations within a distance of k li. If any relay station is not controlled, it can lead to danger—thus, this situation should be completely avoided. The lost letter contained the ingenious deployment plan left by the imperial mathematician, which used the minimum number of squads to control all relay stations.

Xiao F knows that if he can calculate the optimal plan, perhaps he can redeem himself and avoid the death penalty. He turns to you for help. Can you assist him? Of course, while Xiao F waits for your support, he might have already observed some potentially useful properties from the map, which he will tell you through a special method.

Input Format

Read data from standard input.

The first line contains three positive integers n, k, t, representing the number of relay stations, the maximum distance a squad can control, and the identifier for special properties. Refer to the data range for details on special properties.

From the second line to the nth line, each line contains two positive integers \(u_i\), \(v_i\), indicating a path of 1 li between \(u_i\) and \(v_i\).

Output Format

Output to standard output.

Output one line, the minimum number of squads needed for the optimal plan.

Sample Input and Output

Sample Input #1

4 1 0 
1 2 
1 3 
1 4

Sample Output #1

1

Sample Input #2

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

Sample Output #2

2

Notes/Hints

Sample 1 Explanation

As shown in the diagram, since the distance from node 1 to all other nodes is 1, it can control all relay stations.

Sample 2 Explanation

Similar to Sample 1.

Subtasks will provide characteristics of some test data. If you encounter difficulties solving the problem, you can try to solve only some of the test data.

The meaning of t is as follows:
- t = 0: The test point has no additional special properties.
- t = 1: Guarantees that at most 8 nodes have more than one path connected to them.
- t = 2: Guarantees that the distance from all nodes to node 1 is no more than 2.

The scale and characteristics of each test point's data are as follows:

见题面 Input 部分

见题面 Output 部分