Under construction

Still being built. Things may change

Family Tree

Interview

Time limit3sMemory limit2048 MB

Summary
Given a family tree of n people, find the minimum width of a drawing where children sit one level below parents and pictures in a level may shift sideways.
Level

Medium5 of 10

Topics
Tree, BFS
Solved
No attempts yet

Problem

While you are attending the yearly family gathering, you notice that your family keeps growing bigger and bigger. You are having a hard time remembering for every member of the family what their name is and to what part of the family they belong to. To solve this, you decide to create a family tree on a big sheet of paper. You collect a portrait picture from every member of the family and stick them onto the paper in the shape of a tree, putting pictures of children exactly one level below the picture of their parents.

Before actually sticking the pictures on the paper, you need to figure out how much paper you need. Environmentally aware as you are, you try to minimize the amount of paper needed. You decide to allow pictures within the same level to move to the left or right if this makes the tree less wide.

Input

One line with one integer: 2≤n≤1052 \leq n \leq 10^5, the number of people in the family tree.

One line that indicates the earliest ancestor that you have information about.

n−1n - 1 lines, each in the format A - B, indicating that A is the parent of B. These lines have no particular order.

The name of each person consists of at most 20 characters from the English alphabet (A-Z and a-z).

Output

The minimum width of the family tree in the number of portrait pictures.

Examples2

  1. Example 1

    Input
    8
Alice
Alice - Bob
Alice - Carol
Alice - Dave
Bob - Eve
Bob - Frank
Carol - Grace
Carol - Heidi
    Expected output
    4

  2. Example 2

    Input
    8
Alice
Alice - Bob
Alice - Carol
Alice - Dave
Alice - Eve
Bob - Frank
Bob - Grace
Carol - Heidi
    Expected output
    4