A11271 | Rudolf and the Ball Game

The first line of the input contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains three integers $n, m, x$ ( $2 \le n \le 1000$ , $1 \le m \le 1000$ , $1 \le x \le n$ ) — the number of players, the number of throws made, and the number of the player who threw the ball first, respectively.

The next $m$ lines contain information about each throw in order. Each of them contains an integer $r_i$ ( $1 \le r_i \le n - 1$ ) — the distance at which the $i$ -th throw was made, and a symbol $c_i$ , equal to '0', '1', or '?':

- if $c_i$ ='0', then the $i$ -th throw was made clockwise,
- if $c_i$ ='1', then the $i$ -th throw was made counterclockwise,
- if $c_i$ ='?', then Bernard does not remember the direction and the $i$ -th throw could have been made either clockwise or counterclockwise.

It is guaranteed that the sum $n \cdot m$ ( $n$ multiplied by $m$ ) over all test cases does not exceed $2 \cdot 10^5$ .

For each test case, output two lines.

In the first line, output the number of players $k$ ( $1 \le k \le n$ ) who could have the ball at the end of the game.

In the next line, output $k$ numbers $b_i$ ( $1 \le b_i \le n$ ) — the numbers of the players in increasing order. All numbers must be different.

Below is an illustration of three throws for the first test case. The arrows denote possible throw directions. Players who could have the ball after the throw are highlighted in gray.