Một vương quốc có n vùng đất (đánh số 1 đến n) và m mối quan hệ. Mỗi mối quan hệ là một cặp vùng đất u và v với trạng thái t:
- t = 1: u và v phải thuộc cùng lãnh thổ (bạn).
- t = 0: u và v không được thuộc cùng lãnh thổ (kẻ thù). Hãy kiểm tra xem có thể phân chia các vùng đất thành các lãnh thổ sao cho thỏa mãn tất cả mối quan hệ không. Nếu được, in số lãnh thổ ít nhất; nếu không, in -1.
Input:
- Dòng 1: n (số vùng đất, 1 ≤ n ≤ 1000), m (số mối quan hệ, 0 ≤ m ≤ 5000).
- Dòng 2 . .  . m + 1: u v t (u và v là hai vùng đất, t là trạng thái, với 1 ≤ u, v ≤ n, t ∈ {0, 1}).
Output:
- Nếu không thể phân chia: In -1.
- Nếu có thể: In số lãnh thổ ít nhất (số thành phần liên thông sau khi xử lý).