### 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)

It's quiet in here...