Internet Problem Solving Contest

IPSC 2011

Problem K – Keep clicking, keep flipping

The “Flip it” puzzle is played on a board with black and white tiles. In each step you pick a tile, flip it, and also flip all the adjacent tiles (from white to black and vice versa). The goal of this game is to turn all the tiles to their white side. We found this puzzle too easy, so we picked a harder version for you:

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

The first line of each test case contains two integers: n and m. Nodes are numbered from 0 to n - 1. The second line contains a string of length n. The i-th character of this string is either B or W and gives the colour of the i-th node at the beginning of the game. Each of the following m lines contains a pair of nodes xi, yi that are connected by an edge at the beginning of the game.

In the easy data set, n 50, in the hard data set, n 2000.

Output specification

For each test case, output the number of clicks and one particular sequence of clicks that wins the game. If there is no such sequence, output a single line containing the number -1.


3 2  
0 1  
0 2  
7 12  
0 2  
0 3  
1 2  
1 4  
1 6  
2 3  
2 4  
2 6  
3 4  
3 6  
4 5  
5 6
0 2 1  
1 6 3 0 2

Note that in the first test case, if we started by clicking at 1, we would end up stuck with two adjacent white vertices.

The figures below illustrate the solutions for the two test cases.

Test case #1:

Test case #2: