Cho đồ thị vô hướng liên thông có N đỉnh, M cạnh trọng số không âm. Một đường đi từ 1 tới N được phép lặp đỉnh hoặc cạnh; độ dài là XOR trọng số mỗi lần cạnh được đi qua. Hãy tìm độ dài lớn nhất có thể.
Input
Dòng đầu chứa NM.
Mỗi trong M dòng tiếp theo chứa cạnh uvw.
Output
In XOR lớn nhất của một walk từ 1 đến N.
Constraints
1≤N≤5⋅104,1≤M≤105.
0≤w≤1018.
Đồ thị liên thông; cạnh song song và khuyên được phép.
Scoring
Subtask 1 (50% số điểm): N≤8, mọi trọng số nhỏ hơn 32.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
3 3
1 2 1
2 3 2
1 3 7
Output
7
Giải thích: Hai đường cơ bản cho XOR 3 và 7; các vòng lặp chỉ cho phép chuyển giữa hai lớp này nên giá trị lớn nhất là 7.
Lời giải tóm tắt
Mô hình: Cho đồ thị vô hướng liên thông có N đỉnh, M cạnh trọng số không âm. Một đường đi từ 1 tới N được phép lặp đỉnh hoặc cạnh; độ dài là XOR trọng số mỗi lần cạnh được đi qua. Hãy tìm độ dài lớn nhất có thể.
Thuật toán: Duyệt đồ thị từ đỉnh 1, đặt dist[v] là XOR trọng số trên một đường cây từ 1 tới v. Với mỗi cạnh (u,v,w), giá trị cycle = dist[u] xor dist[v] xor w là XOR của một chu trình kín. Chèn mọi cycle vào cơ sở 64 bit.
Thuật toán: Một walk cơ sở từ 1 tới N có XOR dist[N]. Duyệt basis từ bit cao xuống, XOR pivot vào dist[N] khi làm giá trị tăng. Kết quả là maximum trong coset.
Chứng minh đúng: Thêm một chu trình kín vào walk không đổi đầu cuối và XOR thêm đúng giá trị chu trình. Vì có thể ghép các chu trình, mọi dist[N] xor z với z trong span chu trình đều đạt được.
Chứng minh đúng: Ngược lại, XOR đối xứng của một walk bất kỳ với đường cây 1->N làm mọi đỉnh có bậc chẵn trong đa tập cạnh, nên phân rã thành các chu trình; chênh lệch XOR thuộc cycle span. Do đó tập giá trị walk chính xác là coset nói trên. Greedy maximum trên basis cho phần tử lớn nhất của coset.
Độ phức tạp: Duyệt O(N+M), chèn O(64M), bộ nhớ O(N+M).