提示: 欢迎访问OurACM平台。
Problem 1420 Twinkling lights II

Accept: 13    Submit: 60
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Do you remember the problem "Twinkling lights" in FJNUPC 2005? It's a funny problem, Now let's change some conditions to make it a new problem -_- .
There is a line consisting of n lights numbered as 1, 2, …,n. At time 0, some lights are on and the others are off. Light i controls some lights(possibly includes itself). At time t+1, light i will change these lights' status if light i is on at time t. So light j would alter its status(from on to off or from off to on), only if light j is altered by odd times. Please work out how many lights are on at time m.

Input

The first line of the input is an integer T denoting the number of test cases. The first line of each test case consists of two integers separated by one space, where the first integer n (0 < n <= 100) denotes the number of lights and the second integer is m (0 < m <= 1,000,000,000). The second line is a binary string of length n, representing the status of each light at time 0 ("1" denoting the light is on and "0" denoting the light is off). Then follows n lines, the ith line starts with an interger si,which is the number of lights controlled by light i. Then follows si intergers, denoting the lights controlled by light i.

Output

For each test case, output an interger representing the lights that are on at time m.

Sample Input

2 3 2 010 3 1 3 2 1 3 1 1 2 2 11 2 1 2 0

Sample Output

2 0

Hint

The first test case: 010->011->110 The second test case: 11->00->00

Source

FZU ICPC Preliminary Round 2006

Submit  Back  Status  Discuss