Adrian the Wonder Child

Adrian the Wonder Child는 얼마 전 새 프로젝트의 코딩을 시작했다. 그는 매일 Git 저장소에 커밋을 정확히 하나씩 올렸고, 그 결과 저장소는 $n$개의 정점으로 이루어진 트리가 되었다.

Adi에게는 좋은 날과 나쁜 날이 있다. (보통 좋은 날 하루 뒤에 나쁜 날 열 날이 이어지지만, 이 사실은 이 문제에서 중요하지 않다.) 루트(첫 커밋)를 제외한 모든 정점에 대해, 그 정점과 부모를 잇는 간선에 $0$ 또는 $1$ 라벨을 붙인다. 나쁜 날에 올린 커밋이면 $0$, 좋은 날에 올린 커밋이면 $1$이다.

두 정점 사이의 경로에서 같은 값을 가진 연속된 간선이 최대 $k$개이면, 그 경로를 $k$-alternating이라고 한다. Adi는 어느 날이든 생각을 바꿀 수 있으며, 그러면 해당 커밋의 정점과 부모 사이 간선의 라벨이 뒤집힌다.

정수 $m$과 $k$가 주어졌을 때, 라벨을 최대 $m$개의 간선에서 뒤집어 얻을 수 있는 가장 긴 $k$-alternating 경로의 길이를 구하라.

첫 줄에 세 정수 $n$, $k$, $m$이 주어진다 ($3 \leq n \leq 2 \cdot 10^5$, $2 \leq k < n$, $0 \leq m < n$).

다음 $n - 1$개의 줄에는 세 정수 $x$, $y$, $c$가 주어진다 ($1 \leq x, y \leq n$, $c \in \{0, 1\}$). 이는 정점 $x$와 $y$ 사이에 라벨이 $c$인 간선이 있다는 뜻이다. 주어진 간선들은 트리를 이룬다.

라벨을 최대 $m$개의 간선에서 뒤집어 얻을 수 있는 가장 긴 $k$-alternating 경로의 크기를 한 개의 정수로 출력한다.