当前没有测试数据。

Byteasar has had a new palace built. It consists of N chambers and N-1 corridors connecting them. Each corridor connects exactly two chambers. The rooms are numbered from 1 to N. There is only a single entrance to the palace, which leads to chamber no. 1. For each chamber there is exactly one route leading to it from the entrance, without turning back on the way. In other words, the chambers and the corridors form a tree - a connected acyclic graph.

The fire marshal who is to approve the building demands placing fire extinguishers inside. The following are his exact requirements:

• The fire extinguishers should be placed in (some) chambers, and one chamber may store any number of extinguishers.
• Each chamber has to be assigned one fire extinguisher, though it may be stored in another chamber.
• Each fire extinguisher can be assigned to at most S different chambers.
• For each room its assigned extinguisher is within the range of K corridors.

Byteasar has a week spot for lavish palaces, so it is no surprise he has very little money now, right after completion of another splendid palace. Therefore he is interested in the minimum number of fire extinguishers sufficient for satisfying fire marshal's demands.

 

Input

The first line of the standard input contains three integers N, S and K separated by single spaces, 1 <= N <= 100000, 1 <= S <= N, 1 <= K <= 20. Each of the following N-1 lines holds two integers separated by a single space. Line no. i+1 contains the numbers X_i Y_i denoting the corridor connecting chambers no. X_i and Y_i.

Output

The first and only line of the standard output is to hold one integer - the minimum number of fire extinguishers that have to be installed in palace.

Example

For the input data:

12 3 1
1 12
3 8
7 8
8 9
2 12
10 12
9 12
4 8
5 8
8 11
6 8

the correct result is:

4

		<div id="ccontent">
		<!-- google_ad_section_start -->

---

hide comments

<script language="JavaScript">
<!--
$(document).ready(function(){
    $('.pager_link').bind('click', function(me){
            var href=$(me.currentTarget).attr('href');
	$('#ccontent').animate({opacity: 0.5},1);
            $.ajax({
                    type: "GET",
                    url: href+",ajax=1",
                    contentType: "application/x-www-form-urlencoded;charset=ISO-8859-2",
                    success: function(data){
                            $('#ccontent').html(data);
			$('#ccontent').animate({opacity: 1.0},1);
                    },
                    error: function(err){
                            alert('error');
                    }
            });
            return false;
    });
});
-->
</script>




		
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://1rNWaoCz.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/krist7599555">krist7599555</a>: 
							<span style="font-size: 10px; color: #666;">2017-05-18 15:20:25</span>
	<br>
			<p>picture

http://main.edu.pl/en/archive/oi/16/gas
=(Francky)=> Thanks. Added in body, no copyright infringement intended. To be removed if need.

Last edit: 2017-05-18 16:28:15 </td> </tr></p>

		<!-- google_ad_section_end -->
		</div>
		<table width="100%">
            <tbody><tr>
            <td colspan="2" height="20px"></td>
    </tr>
    <form method="post" action="/comment/STC01/add/"></form>
    <tr> <td style="" colspan="2">Leave a Comment</td> </tr>
    <tr>
            <td valign="top"></td>
            <td><textarea name="content" rows="3" class="form-control"></textarea></td>
    </tr>
    <tr>
            <td colspan="2" style=""><br>
                    <input type="submit" value="Publish" class="btn btn-default">
                    <input type="hidden" name="pcode" value="STC01">
            </td>
    </tr>

<tr> <td colspan="2">
Notes:
1. Don't post any source code here.
2. Please be careful, leave short comments only. Don't spam here.
3. For more discussion (hints, ideas, solutions) please visit our forum.
4. Authors of the problems are allowed to delete the post and use html code here (e.g. to provide some useful links). </td> </tr>

    </tbody></table>