2010 Canadian Computing Competition, Stage 2

Day 1, Problem 2: Tree Pruning

We are given a rooted tree with N nodes in which each node has at most two children. (Yes, Jacob, at most two.) Each node may be black or white. We define a "prune" as the deletion of a node and the subtree rooted at that node from the tree. Given an integer D, find the minimum number of "prunes" required to obtain a tree in which the number of white nodes minus the number of black nodes is exactly D, or determine that it is impossible to do so.

Input

The first line of input will contain two integers N (1 ≤ N ≤ 300) and D (-N ≤ D ≤ N), representing the number of nodes in the tree and the required difference, respectively. The next N blocks of input each contain the description of a node. The first line of each block contains three integers: the id of the node (a unique integer between 0 and N-1), the colour of the node (1 for a white node, 0 for a black node) and an integer C that represents the number of children of the node. C lines follow, each one containing an integer that represents the id of one child. The root of the tree is the node with id 0.

Output

On one line, output the minimum number of "prunes", as mentioned in the problem description. If it is impossible to obtain the required difference D, output -1.

Sample Input

6 3
0 1 2
1
3
1 1 2
2
5
2 1 1
4
3 1 0
4 0 0
5 1 0

Sample Output

1

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: May 19, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)