Единственное отличие этой задачи от D2 — ограничение на размер дерева.
Вам дано некорневое дерево с \(n\) вершинами. В этом дереве есть некоторая скрытая вершина \(x\), которую вы пытаетесь найти.
Для этого вы можете задать \(k\) запросов \(v_1, v_2, \ldots, v_k\), где \(v_i\) — вершины дерева. После того, как вы закончили задавать все запросы, вам дается \(k\) чисел \(d_1, d_2, \ldots, d_k\), где \(d_i\) — количество ребер на кратчайшем пути между \(v_i\) и \(x\). Обратите внимание, что вы знаете, какое расстояние соответствует какому запросу.
Найдите минимальное \(k\), при котором существуют некоторые запросы \(v_1, v_2, \ldots, v_k\), позволяющие всегда однозначно определить \(x\) (независимо от того, какой \(x\) выбран).
Обратите внимание, что выводить эти запросы не нужно.
Примечание
В первом наборе входных данных есть только одна вершина, поэтому никаких запросов не требуется.
Во втором наборе входных данных достаточно задать единственный запрос о вершине \(1\). Тогда, если \(x = 1\), вы получите \(0\), в противном случае — \(1\).