pinkandblue

Xenny là một giáo viên và ông có  N  học sinh.  N  đứa trẻ đang ngồi trong một căn phòng. Mỗi đứa trẻmặc   áo phông  trắng , trên đó có ghi một số duy nhất  từ  ​​1 đến N.  Xenny sẽ phát  áo phông  màu hồng  và  xanh cho học sinh. Điều này khiến học sinh rất vui.

Xenny cảm thấy rằng việc phân phối ngẫu nhiên Áo phông sẽ rất nhàm chán. Vì vậy, anh quyết định giữ một điều kiện thú vị:

Mỗi học sinh sẽ nhận được một chiếc áo phông có màu khác với bạn bè của mình. Nghĩa là, nếu  X và Y  là  bạn  và X có một chiếc áo phông màu hồng, thì Y bắt  buộc phải  có một chiếc áo phông màu xanh, và ngược lại.

Ngoài ra, Xenny còn tin rằng con trai nên mặc áo phông xanh và con gái nên mặc áo phông hồng. Nếu một bé trai được tặng áo phông hồng hoặc một bé gái được tặng áo phông xanh, ông gọi đó là sự  đảo ngược .

Vì vậy, Xenny muốn phân phối Áo phông theo cách thú vị nêu trên và cũng muốn giảm thiểu "sự đảo ngược". Hãy giúp anh ấy giải quyết nhiệm vụ.

Lưu ý: Không có nhóm bạn nào không giao nhau trong phòng. Nghĩa là không tồn tại 2 nhóm riêng biệt với số lượng học sinh hữu hạn, nhưng chỉ tồn tại đúng 1 nhóm học sinh trong tình huống đã cho.

 

Đầu vào
Dòng đầu tiên là số lượng trường hợp thử nghiệm T.

Dòng đầu tiên của mỗi trường hợp kiểm tra chứa 2 số nguyên cách nhau bởi dấu cách -  N  và  M  - lần lượt là số học sinh và số tình bạn có mặt.

Dòng thứ hai gồm  N ký tự cách nhau bằng dấu cách , trong đó ký tự thứ i  biểu thị giới tính của học sinh thứ i  .  B: Nam, G: Nữ .

Tiếp theo là M dòng  . Mỗi dòng gồm 2 số nguyên cách nhau bởi dấu cách,  u và v , thể hiện rằng  u  là bạn của  v  và ngược lại.

 

Đầu ra
Nếu Xenny có thể phân phối Áo phông theo cách mong muốn, hãy in ra   số  lần đảo ngược tối thiểu  cần thiết. Nếu không, hãy in ra -1.

 

Ràng buộc
1 ≤  N  ≤ 10 5
1 ≤  M  ≤ 10 5
1 ≤  u, v  ≤ N

Màu sắc của áo phông được thể hiện bằng các ký tự viết hoa  'B'  và  'G'

 

Vật mẫu

 

Đầu vào

3

3 2

BGB

1 2

1 3

6 9

BBBGGG

3 5

2 6

4 2

6 3

3 1

3 4

6 1

5 1

1 4

6 5

GGGBG G

6 3

1 3

2 3

4 3

5 3

 

Đầu ra 

1

-1

2

 

Giải thích

#1

Học sinh 1 có thể được tặng một chiếc áo phông màu xanh. Do đó, Học sinh 2 và 3 sẽ nhận được áo phông màu hồng. Vì Học sinh 3 là con trai và đã nhận được một chiếc áo phông màu hồng, nên số lần đảo ngược = 1.