TOJ-1319 Odd Loving Bakers

There is a group of n (1 ≤ n ≤ 100) bakers in the town of Utopia. These bakers hold a monthly celebration in which they award a prize to some of the luckier among themselves. These lucky guys are chosen as follows:

In the beginning there are some chalk marks on some of the bakers' houses. Each baker has a list of his/her favorite bakers. After each celebration each of the winners puts a chalk mark on the house of all the bakers in his/her favorite list. Before each celebration those bakers with an odd number of chalk marks on their house will be chosen as winners. As there will be a great prize for the winners of the t^th (1 ≤ t ≤ 1,000,000,000) celebration, you are asked to find the number of its winners.

Input

The first line of the input file contains a single integer X (1 ≤ X ≤ 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows:

The first line of each instance contains two integers n (the number of bakers) and t (the number of the celebration we want the winners of).

The next n lines of the instance each describe a baker. In each of these lines first comes the name of the baker (names are lower case strings of no more than 20 characters without spaces), then comes the number of chalk marks initially on the baker's house, then comes the number of bakers in this baker's favorite list, and after that come the names of the bakers in this baker's list.

Output

There should be one line per test case. For each test case write a line containing a single integer, the number of the winners of the t^th celebration.

Sample Input

2
3 2
bessie 2 3 bessie linda mary
mary 1 1 linda
linda 0 1 bessie
2 2	
siavosh 1 2 siavosh mohammad 
mohammad 1 0

Sample Output

2
0

Source: Tehran 2004 Iran Nationwide

所有baker的初始状态可用一个n*1矩阵表示，此矩阵乘一个单位矩阵不会改变，在单位矩阵的基础上，我们将第i行视为第i个baker在有权标记时对各个baker的动作。

以第一组样例为例，初始状态A：[2,0,1]，动作矩阵 B：|2,1,1|，顺序为bessie，linda，mary。初始状态为偶数的无论怎样乘动作矩阵所得状态仍为偶数，则两矩阵相乘

　　　　　　　　　　　　　　　　　　　 |1,1,0|

　　　　　　　　　　　　　　　　　　　　　　　　 |0,1,1|

所得结果[x,y,z]中，x=2*2+0*1+1*0，表示此轮动作中mary对bessie无动作（动作矩阵3，1处为偶数），bessie和linda本轮不能动作（状态矩阵中前两位为偶数）。

结果中奇数为我们要计数的目标，而欲得奇数，唯有奇数乘奇数，奇数加偶数（这里体会两个矩阵相乘的意义）。根据题意，一轮动作结果为A，即AB^0，t轮结果即AB^(t-1).

#include<iostream>  
#include<memory.h>  
#include<string>  
#include<map>  
using namespace std;
struct matrix{short m[102][102];
}a,b;  
int x,n,t;
map<string,int> name;
void om(matrix a){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<a.m[i][j]<<" ";}cout<<endl;}
}
matrix mm(matrix a,matrix b){matrix temp;memset(temp.m,0,sizeof(temp.m));//om(a);om(b);for(int i=1;i<=n;i++)  {  for(int j=1;j<=n;j++) {  for(int k=1;k<=n;k++)  temp.m[i][j] = (temp.m[i][j] + a.m[i][k] * b.m[k][j])%2;  }  }//om(temp);  return temp; 
}
matrix mp(int t)  
{  matrix temp;memset(temp.m,0,sizeof(temp.m));  for(int i = 1; i<=n; i++)  {  temp.m[i][i] = 1;  }  while(t)  {  if(t%2) temp = mm(temp,b);  t = t/2;  b = mm(b,b);  }  return temp;  
}
int main(){int i,j,k,e,g,f,d,h;string s;cin>>x;while(x--){cin>>n>>t;e = n;memset(a.m,0,sizeof(a.m));memset(b.m,0,sizeof(b.m));name.clear();k = 0;for(i=1;i<=n;i++)    b.m[i][i] = 1;while(e--){cin>>s>>h>>d;if(name.find(s)==name.end()){k++;name[s] = k;}g = name[s];a.m[1][g] = h;while(d--){cin>>s;if(name.find(s)==name.end()){k++;name[s] = k;}f = name[s];b.m[g][f]++;}}b = mp(t-1);a = mm(a,b);int ans = 0;  for(int i = 1; i<=n; i++)  {  if(a.m[1][i]%2) ans++;  }cout<<ans<<endl;}return 0;
}