This page is still under construction.

Parts of this page are still being built. What you see may change.

Special Ice Breaking Penguin

Time limit1sMemory limit1024 MB

Summary
Given a tree with some nodes marked as supports, break as many nodes as possible while keeping the penguin's node connected to at least two supports through unbroken ordinary nodes.
Level

Hard8 of 10

Topics
Tree, DFS, Greedy, Dynamic programming
Solved
No attempts yet

Problem

Dodo was bored, so he went to a board game cafe. A board game called Special Ice Breaking Penguin, an upgraded version of the Ice Breaking Penguin he used to enjoy, had just come out, so he decided to play it himself. The game comes with special glasses, and when you wear them and look at the ice, you can see the connections between the ice blocks.

There are two kinds of ice in Special Ice Breaking Penguin: ice that acts as a support and ordinary ice. Ice that acts as a support appears red, and it holds up ordinary ice so that the ordinary ice does not break. An ordinary ice block does not break even if only one support is connected to it, but the ice block the penguin is standing on does not break only if two or more ice blocks acting as supports are connected to it. Here, a support being connected means that a connection path leads from the support through distinct ordinary ice blocks. In Special Ice Breaking Penguin, what is the maximum number of ice blocks Dodo can break without dropping the penguin?

Input

The first line gives the number of ice blocks NN (3≤N≤328 0003 \leq N \leq 328\,000), the number of ice blocks that act as supports SS (2≤S≤N−12 \leq S \leq N-1), and the number of the ice block the penguin is on PP (S<P≤NS < P \leq N). When the number of ice blocks that act as supports is SS, ice blocks 11 through SS act as supports.

Each of the next N−1N-1 lines gives two integers AA and BB. This means ice block AA and ice block BB are connected, and the same connection is not given more than once.

When the game starts, the penguin is on an ordinary ice block and no ice block is broken. Each ice block has an integer number from 11 to NN, and there is exactly one path between any two distinct ice blocks. Also, there is no case where two distinct supports are connected without passing through the ice block the penguin is on.

Output

Find the maximum number of ice blocks the player can break without dropping the penguin. Ice blocks that act as supports also count as ice blocks that can be broken.

Examples1

  1. Example 1

    Input
    21 6 12
    1 9
    1 10
    10 12
    2 13
    13 11
    11 12
    3 8
    8 7
    8 12
    5 19
    5 14
    14 12
    6 20
    6 21
    20 15
    15 12
    4 18
    4 17
    17 16
    16 12
    
    Expected output
    16