Odd Loving Bakers

Time limit1sMemory limit128 MB

Summary

Simulate monthly celebrations where bakers with an odd chalk count win and add marks to their favorite bakers; find the number of winners at celebration t up to 1e9.

Level: Medium7 of 10
Topics: Bit manipulation, Math, Graph, Simulation
Solved: No attempts yet

Problem

A town has $N$ bakers. Every month they hold a celebration and award a prize to some of them, chosen as follows.

At the start, chalk marks are drawn on the houses of some bakers. Each baker keeps a list of favorite bakers. Right before each celebration, every baker whose house currently has an odd number of chalk marks becomes a winner of that celebration. Immediately after the celebration, each winner adds one chalk mark to the house of every baker on their own favorite list.

Given the initial chalk marks and every baker's favorite list, determine how many winners the $t$ -th celebration has.

Input

The first line contains an integer $X$ ( $1 \le X \le 11$ ), the number of test cases. Each test case has the following form:

The first line contains two integers $n$ and $t$ : the number of bakers, and the index of the celebration whose winners must be counted.
Each of the next $n$ lines describes one baker: the baker's name (a lowercase string of at most 20 characters with no spaces), then the number of chalk marks initially on that baker's house, then the number of bakers on that baker's favorite list, followed by those bakers' names.

Output

For each test case, print a single line with one integer: the number of winners of the $t$ -th celebration.

Constraints

$1 \le n \le 100$
$1 \le t \le 10^9$
$0 \le$ the initial number of chalk marks on a baker's house $< 100$

Examples8

Example 1

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

Expected output

2
0

Example 2

Input

1
4 1
alpha 3 0
beta 4 0
gamma 7 1 alpha
delta 0 1 beta

Expected output

Example 3
Input
```
1
3 5
a 2 1 b
b 10 1 c
c 4 1 a
```
Expected output
```
0
```

Example 4

Input

1
5 1000000000
p 1 0
q 2 0
r 3 0
s 4 0
u 5 0

Expected output

Example 5
Input
```
1
1 1000000000
solo 1 1 solo
```
Expected output
```
0
```

Example 6

Input

3
1 1
solo 1 1 solo
1 1000000000
solo 1 1 solo
2 3
a 1 1 b
b 0 1 a

Expected output

1
0
0

Example 7

Input

1
6 1000000000
a 1 2 b c
b 1 2 c d
c 1 2 d e
d 1 2 e f
e 1 2 f a
f 1 2 a b

Expected output

Example 8

Input

1
5 7
u 3 2 v w
v 0 1 x
w 5 3 x y u
x 2 0
y 1 2 u v

Expected output