입자 가속기

KOI 연구소는 입자 가속기를 이용하여 연구를 진행하고 있다. KOI 연구소의 입자 가속기는 $N$개의 방과 방들을 잇는 $N-1$개의 양방향 통로로 이루어져 있으며, 임의의 서로 다른 두 방들을 통로만을 사용하여 오갈 수 있다. 즉, KOI 연구소의 입자 가속기는 트리 구조를 이룬다.

입자 가속기의 방들에는 $0$부터 $N-1$까지의 서로 다른 번호가 붙어 있으며, 입자 가속기의 통로들에는 $0$부터 $N-2$까지의 서로 다른 번호가 붙어 있다. 모든 $0 \le i \le N-2$에 대해 $i$번 통로는 $A[i]$번 방과 $B[i]$번 방을 연결한다.

최근 KOI 연구소는 IOI 입자 충돌 실험을 진행하고 있다. IOI 입자는 생성하는 것도 매우 어렵기 때문에, 입자 가속기의 방마다 최대 $1$개씩만 생성을 시도할 수 있다. 어떤 방에서 IOI 입자를 생성하는 데 성공하면 IOI 입자 $1$개가 그 방에 정지한 상태로 존재하게 된다. 반대로, IOI 입자를 생성하는 데 실패하면 실험 장비 점검을 위해 그 방은 폐쇄되어 사용할 수 없게 된다.

KOI 연구소는 몇 개의 방을 골라 IOI 입자 생성을 시도한 후 실험을 진행하고자 한다. 실험은 여러 번의 충돌 실험이 순차적으로 진행되는 형태이며, 각 충돌 실험에서는 IOI 입자가 있는 방 $2$개를 골라 IOI 입자 충돌 실험을 진행한다. 이때, 선택된 방을 연결하는 경로 위에 IOI 입자가 있는 방이 있어서는 안 되며, IOI 입자 생성에 실패한 방이 있어서도 안 된다. IOI 입자 충돌 실험을 진행하고 나면 충돌 실험에 사용된 두 입자는 소멸한다. IOI 입자 생성에 성공했지만 IOI 입자가 더 이상 존재하지 않는 방의 경우, 추후 진행되는 충돌 실험에서 선택된 $2$개의 방을 연결하는 경로 위에 존재해도 된다는 점에 유의하라.

여러분은 KOI 연구소가 충돌 실험을 최대 몇 회 진행할 수 있는지 구해야 한다. 초기에는 입자 가속기의 모든 방에 IOI 입자가 없으며, 모든 방에 대해 IOI 입자 생성을 시도할 수 있다. KOI 연구소는 총 $Q$번 IOI 입자 생성을 시도하며, 여러분은 각 생성 시도마다 현재 상태에서 실험을 진행할 경우 충돌 실험을 최대 몇 회 진행할 수 있는지 구해야 한다.

입자 가속기

문제

제한