시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 512 MB7217610.000%

문제

You are given n binary strings s1, . . . , sn, each of the same length m. Along with each si you are given a bit bi. You are also given some nonnegative integer k and want to know whether there exists a subset S of {0, 1, . . . , m−1} of size at most k such that for each i = 1, 2, . . . , n, the bit bi is the XOR of the bits of si at the indices in S. The si are 0-indexed strings. Recall that the XOR of a set of bits is 1 if the number of bits equal to 1 is odd, else the XOR is 0 (in particular, the XOR of an empty set of bits is 0).

For example, if s1 = 1010 and S = {0, 3}, then b1 would be 1 (the first bit of s1) XOR’d with 0 (the last bit of s1), which is 1.

Given n, k, and the strings s1, . . . , si and their corresponding bi, find a set S of size at most k which produces the given bi. You should also detect when no such S exists.

입력

The first line contains n and k, space-separated (1 ≤ n ≤ 64, 0 ≤ k ≤ 10). n lines then follow, where the ith line contains si, followed by a space, then bi. In a given test case all strings si are of the same length m (1 ≤ m ≤ 50). k will not be bigger than m.

출력

If no set S of size at most k exists producing the given bi, output −1 followed by a newline. Otherwise, on the first line output the size of a possible S. If the size of that S is not 0, on the second line, output a space-separated list of the indices in S, followed by a newline. If there exist multiple valid S to be output, you can output any one of your choosing.

예제 입력 1

3 1
111 1
001 0
011 1


예제 출력 1

1
1


예제 입력 2

4 7
010001000111100011010010000011110000000000 0
001101010101000101001011110001101010101111 0
100111100101100000110000110110010110100101 0
011010001110101111000000111101100010111111 1


예제 출력 2

3
0
1
19