33084번 - Walking Around 다국어

문제

You are given a weighted tree with $N$ vertices, numbered from 1ドル$ to $N$. The edges are numbered from 1ドル$ to $N - 1,ドル where edge $i$ connects two vertices $U_i$ and $V_i$ with a weight of a non-negative integer $W_i$.

A path in the tree is defined as a sequence of unique vertices $(u_0, u_1, \dots , u_m)$ for some $m ≥ 1$ such that each pair of adjacent vertices, $(u_j , u_{j+1})$ for all 0ドル ≤ j < m,ドル is connected by an edge in the tree. Define the score of a path $(u_0, u_1, \dots , u_m)$ as the bitwise XOR of the weight of all edges in the path, i.e. $\text{XOR}(w_0, w_1, \dots , w_{m-1})$ where $w_j$ is the weight of the edge that connects $u_j$ and $u_{j+1}$ (for all 0ドル ≤ j < m$).

Your task is to find the minimum and the maximum score of any path that can be obtained from the given tree.

For example, the minimum and the maximum score of any path in the following tree are path $(4, 2, 1)$ with a score of $\text{XOR}(2, 3) = 1,ドル and path $(5, 2, 1, 3)$ with a score of $\text{XOR}(8, 3, 4) = 15,ドル respectively.

입력

Input begins with an integer $N$ (2ドル ≤ N ≤ 100,円 000$) representing the number of vertices in the given tree. Each of the next $N - 1$ lines contains three integers $U_i$ $V_i$ $W_i$ (1ドル ≤ U_i < V_i ≤ N$; 0ドル ≤ W_i ≤ 10^9$) representing edge $i$.

출력

Output two space-separared integers in a single line, representing the minimum and the maximum score of any path that can be obtained from the given tree in that order.

제한

힌트