В последнее время Влад увлёкся остовными деревьями, так что его друзья не долго думая подарили ему на день рождения связный взвешенный неориентированный граф из \(n\) вершин и \(m\) рёбер.
Влад определил орность остовного дерева как побитовое ИЛИ всех его весов и теперь его интересует, какова минимальная возможная орность, которой можно добиться, выбрав некоторое остовное дерево. Остовное дерево — связный подграф данного графа, не содержащий циклов.
Иными словами вы хотите оставить \(n-1\) ребро, так чтобы граф остался связным и побитовое ИЛИ весов рёбер было как можно меньше. Вы должны найти само побитовое ИЛИ.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных — минимальную возможную орность остовного дерева.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3
1 2 1
2 3 2
1 3 2
5 7
4 2 7
2 5 8
3 4 2
3 2 1
2 4 2
4 1 2
1 2 2
3 4
1 2 1
2 3 2
1 3 3
3 1 4
|
2
10
3
|