Under construction

Still being built. Things may change

Fix the Tree

Time limit1sMemory limit1024 MB

Summary
Given a tree with some broken vertices, repair at most K of them to maximize the number of vertices that still work, where a vertex works only if no ancestor is broken.
Level

Medium6 of 10

Topics
Tree, Dynamic programming, Sorting
Solved
No attempts yet

Problem

A rooted tree with NN vertices has vertex 1 as its root. Each vertex is numbered with a distinct integer from 11 to NN. The tree has MM broken vertices. A broken vertex does not work, and neither do its descendants, whether or not they are broken. In other words, a vertex does not work if at least one of its ancestors is broken.

Repair at most KK broken vertices to maximize the number of vertices that work.

Input

The first line contains three integers NN (1≤N≤1051\leq N\leq 10^5), MM (1≤M≤N1\leq M\leq N), and KK (1≤K≤101\leq K\leq 10), separated by spaces. NN is the number of vertices, MM is the number of broken vertices, and KK is the maximum number of vertices you can repair.

Each of the next N−1N-1 lines contains two distinct vertices uu and vv (1≤u,v≤N1\leq u,v\leq N), separated by a space, that are connected by an edge.

The line after those contains the MM numbers of the broken vertices, separated by spaces. All MM numbers are distinct.

Output

Print the maximum number of working vertices you can get by repairing at most KK broken vertices.

Examples1

  1. Example 1

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