Đất nước ~X~ là một quốc gia phát triển, đặc biệt là trong lĩnh vực khoa học công nghệ và logistics. Để tiếp tục phát triển đất nước hơn nữa, một trong những chính sách ưu tiên cần thực hiện ngay đó là xây dựng một mạng lưới đường bộ mới. Giữa một số cặp thành phố có các con đường một chiều, con đường thứ ~i~ dẫn từ thành phố ~u_i~ đến thành phố ~v_i~ có độ dài ~w_i~. Hai thành phố chính của ~X~ có số hiệu ~a~ và ~b~.

Người dân đất nước ~X~ rất yêu tổ quốc của mình, họ thích tính toán mọi đặc trưng trong đó. Một trong những đặc trưng yêu thích của họ là "vẻ đẹp". Họ gọi "vẻ đẹp của một đường đi" là phép XOR theo từng bit của độ dài tất cả các con đường trên đường đi đó. Còn "vẻ đẹp của đất nước" họ gọi là phép XOR theo từng bit của vẻ đẹp của tất cả các đường đi từ thành phố ~a~ đến thành phố ~b~. Có thể có vô số đường đi như thế và đường đi này có thể đi qua cùng một thành phố nhiều lần.

Người dân muốn biết vẻ đẹp của đất nước của mình bằng bao nhiêu và yêu cầu bạn tính giá trị này hoặc trả lời cho họ biết là không thể tính được vẻ đẹp của đất nước họ dựa trên các số liệu họ cung cấp.

Phép XOR theo từng bit của một tập hợp các số được gọi là phép XOR theo từng bit của tất cả các số khác ~0~ trong tập hợp đó. Nếu trong tập hợp có vô số số khác ~0~, thì không thể tính phép XOR theo từng bit.

Phép XOR theo từng bit (hay phép cộng từng bit modulo ~2~) là một phép toán nhị phân, kết quả của phép toán tương đương phép XOR logic cho từng cặp bit đứng ở cùng vị trí trong biểu diễn nhị phân của các toán hạng. Nói cách khác, nếu các bit tương ứng của các toán hạng khác nhau, thì bit nhị phân tương ứng của kết quả bằng ~1~; nếu các bit giống nhau, thì bit nhị phân của kết quả bằng ~0~.

Ví dụ, nếu ~x = 109_{10} = 1101101_2~ và ~y = 41_{10} = 101001_2~, thì phép XOR theo từng bit của chúng bằng ~x \oplus y = 1000100_2 = 68_{10}~.

Đường đi trong đồ thị được gọi là một dãy các đỉnh, trong đó bất kỳ hai đỉnh liên tiếp nào đều được nối bằng một cạnh.

Input

• Dòng đầu tiên chứa một số nguyên ~t~ ~(1 \le t \le 40\,000)~ là số bộ dữ liệu đầu vào. Mỗi bộ dữ liệu có cấu trúc được mô tả như sau:

  • Dòng đầu chứa hai số nguyên ~n~ và ~m~ ~(1 \le n, m \le 200\,000)~ tương ứng là số thành phố và số con đường ở đất nước ~X~.

  • Trong ~m~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~u_i, v_i~ và ~w_i~ ~(1 \le u_i, v_i \le n, 0 \le w_i \le 2^{30} - 1)~.

  • Dòng cuối chứa hai số nguyên ~a~ và ~b~ ~(1 \le a, b \le n)~.

• Ký hiệu ~P_n~ là tổng ~n~, và ~P_m~ là tổng ~m~ trên tất cả các bộ dữ liệu đầu vào trong một test. Dữ liệu đảm bảo ~P_n \le 200\,000~ và ~P_m \le 200\,000~.

Output

Với mỗi bộ dữ liệu đầu vào, in ra một số nguyên là vẻ đẹp của đất nước ~X~ trên một dòng. Nếu không có đáp án, thì in ~-1~.

Scoring

Sample Input 1

4
1 1
1 1 0
1 1
3 5
1 2 0
1 2 1
1 2 3
2 3 5
2 3 2
1 3
2 2
1 2 1
2 1 2
1 2
3 3
1 2 7
2 3 0
3 1 7
2 3

Sample Output 1

0
7
-1
0

Notes

Trong bộ dữ liệu đầu tiên, trong nước chỉ có một con đường có độ dài ~0~, do đó vẻ đẹp của bất kỳ đường đi nào đều bằng ~0~, và khi đó phép XOR theo từng bit của vẻ đẹp của tất cả các đường đi bằng ~0~.

Trong bộ dữ liệu thứ hai, trong nước có tổng cộng ~6~ đường đi có thể từ thành phố ~1~ đến thành phố ~3~, vẻ đẹp của chúng bằng: ~0 \oplus 5 = 5~, ~0 \oplus 2 = 2~, ~1 \oplus 5 = 4~, ~1 \oplus 2 = 3~ và ~3 \oplus 5 = 6~, ~3 \oplus 2 = 1~. Khi đó vẻ đẹp của đất nước: ~5 \oplus 2 \oplus 4 \oplus 3 \oplus 6 \oplus 1 = 7~.

Trong bộ dữ liệu thứ ba, từ thành phố ~1~ đến thành phố ~2~ có các đường đi có vẻ đẹp ~1~, ~1 \oplus 2 \oplus 1 = 2~, ~1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 = 1~, ~1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 = 2, \dots~ Khi đó từ thành phố ~1~ đến thành phố ~2~ có vô số đường đi với vẻ đẹp khác không, và do đó không thể tính được đáp án.

Trong bộ dữ liệu thứ tư, từ đỉnh ~2~ đến đỉnh ~3~ có vô số đường đi có vẻ đẹp ~0~, và không có đường đi nào có vẻ đẹp khác không. Khi đó vẻ đẹp cuối cùng của đất nước bằng ~0~.