Adrian the Wonder Child

Adrian the Wonder Child started coding for his new project a while ago. Each day he pushed exactly one commit to his Git repository, so the repository now forms a tree with $n$ vertices.

Adi has good days and bad days. (Usually one good day is followed by ten bad days, but that fact does not matter for this problem.) For every vertex except the root (the initial commit), he labels the edge to its parent with $0$ or $1$. The label is $0$ if he pushed that commit on a bad day and $1$ if he pushed it on a good day.

A path between two vertices is $k$-alternating if it has at most $k$ consecutive edges with the same label. Adi can change his mind about any day, which flips the label of the edge between that commit's vertex and its parent.

Given integers $m$ and $k$, find the length of the longest $k$-alternating path that can be obtained by flipping the labels of at most $m$ edges.

The first line contains three integers $n$, $k$, and $m$ ($3 \leq n \leq 2 \cdot 10^5$, $2 \leq k < n$, $0 \leq m < n$).

Each of the next $n - 1$ lines contains three integers $x$, $y$, and $c$ ($1 \leq x, y \leq n$, $c \in \{0, 1\}$), meaning there is an edge between $x$ and $y$ with label $c$. The given edges form a tree.

Print a single number: the size of the longest $k$-alternating path that can be obtained by flipping the labels of at most $m$ edges.