Tô màu đồ thị

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Ban đầu mỗi cạnh được tô màu đỏ (R) hoặc xanh (B).

Trong mỗi lượt, bạn chọn một đỉnh và đảo màu tất cả các cạnh kề với đỉnh đó: mọi cạnh đỏ kề đỉnh này chuyển thành xanh, và mọi cạnh xanh kề đỉnh này chuyển thành đỏ.

Hãy tìm số lượt ít nhất để làm cho tất cả các cạnh có cùng một màu.

Đồ thị không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh lặp (giữa hai đỉnh có nhiều nhất một cạnh).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$, $v_i$ và một ký tự $c_i$: cạnh nối đỉnh $u_i$ với $v_i$ có màu ban đầu là $c_i$ (R nếu đỏ, B nếu xanh).

Dữ liệu ra

• Nếu không thể làm cho tất cả các cạnh cùng màu, in ra $-1$.
• Ngược lại, dòng đầu in số lượt ít nhất $k$; dòng thứ hai in $k$ số nguyên là chỉ số các đỉnh được chọn (theo thứ tự bất kỳ). Nếu có nhiều phương án tối ưu, in ra bất kỳ phương án nào.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $c_i\in \{R,B\}$

Ví dụ