Дан связный неориентированный граф без циклов (то есть дерево) на $$$n$$$ вершинах, при этом на каждом ребре написано какое-то целое неотрицательное число.

Рассмотрим все пары вершин $$$(v, u)$$$ (то есть всего $$$n^2$$$ таких пар) и для каждой пары посчитаем побитовое исключащее ИЛИ (xor) всех чисел на рёбрах на простом пути между $$$v$$$ и $$$u$$$. Если путь состоял только из одной вершины, то xor всех чисел на рёбрах этого пути считается равным $$$0$$$.

Предположим, мы отсортировали полученные $$$n^2$$$ значений по неубыванию. Требуется вывести $$$k$$$-е из них.

Операция xor определяется следующим образом:

Пусть даны два целых неотрицательных числа $$$x$$$ и $$$y$$$, рассмотрим их двоичные записи (возможно с ведущими нулями): $$$x_k \dots x_2 x_1 x_0$$$ и $$$y_k \dots y_2 y_1 y_0$$$ (где $$$k$$$ любое число, что все биты $$$x$$$ и $$$y$$$ могут быть представлены). Здесь $$$x_i$$$ это $$$i$$$-й бит числа $$$x$$$, а $$$y_i$$$ это $$$i$$$-й бит числа $$$y$$$.

Пусть $$$r = x \oplus y$$$ — результат операции xor над числами $$$x$$$ и $$$y$$$. Тогда двоичной записью $$$r$$$ будет $$$r_k \dots r_2 r_1 r_0$$$, где:

$$$$$$ r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. $$$$$$