Milk Multidrink

Byteasar lives in Byteburg, a city with a milk bar at every intersection. One day he came up with the idea of a milk multidrink: he wants to visit every milk bar in the city exactly once. He does not want to walk far after finishing a drink, so the next bar on his route has to be at most two blocks away from the intersection he is standing at. The distance between two intersections is the number of streets on the shortest route between them.

The intersections are numbered $1$ through $n$ and every street is bidirectional. Between any two intersections there is exactly one route that never visits the same intersection twice. Byteasar starts at intersection $1$ and finishes at intersection $n$.

Decide whether an order of visits that meets his requirements exists.

In the city drawn above, visiting the bars in the order 1, 11, 8, 7, 5, 9, 2, 10, 4, 6, 3, 12 meets the requirements.

For the city drawn above no order meets the requirements.

The first line contains one integer $n$, the number of intersections in Byteburg ($2 \le n \le 500000$).

Each of the next $n-1$ lines holds two distinct integers $a_i$ and $b_i$ separated by a single space ($1 \le a_i, b_i \le n$). They describe the street that links intersections $a_i$ and $b_i$.

Print TAK on a single line if at least one order of visits meets Byteasar's requirements, and BRAK otherwise. TAK is Polish for yes and BRAK is Polish for none.