Дан неориентированный граф со взвешенными рёбрами. Длина некоторого пути между двумя вершинами равна побитовому исключающему или весов всех рёбер, по которым проходит путь (если некоторое ребро используется в пути несколько раз, то столько же раз оно учитывается в длине пути). Вам необходимо найти минимально возможную длину пути между вершиной 1 и вершиной n.
Обратите внимание, что граф может содержать кратные рёбра и/или петли. Гарантируется, что граф связный.
Выходные данные
Выведите одно число — минимально возможную длину пути между вершинами 1 и n.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 3
1 3 2
3 2 0
|
2
|
|
2
|
2 2
1 1 3
1 2 3
|
0
|