For the first subtask, we only need to check if it is possible to convert the given item to item ~1~. If yes, Dankey Kang must steal this item, and the answer is ~1~. Otherwise, the answer is ~0~.

We only store the recipes that require exactly ~1~ item, and we keep following the recipes until no new recipe can be followed. However, this can result in an infinite loop. There is an infinite loop if you can follow the recipes ~M+1~ times, and an infinite loop means that Dankey Kang could ruin Fax's Thanksgiving by stealing ~0~ items.

It is easy to determine if the newly produced item is item ~1~.

Time Complexity: ~\mathcal{O}(N)~

In each recipe, the target item is the parent of all items in the list. From the problem statement, an item has at most ~1~ parent. An item is called a leaf if it is not a parent of any other item. If we draw out all the parent-child edges, there will be a rooted tree at item ~1~, because item ~1~ does not have a parent. The diagram below shows Sample Input 1.

For the second subtask, Dankey Kang's optimal strategy is to find the shortest path from item ~1~ to a leaf, then steal all items in the path (including item ~1~ and the leaf). The length of the shortest path can be easily calculated with a basic graph search algorithm, such as BFS or DFS.

Time Complexity: ~\mathcal{O}(N)~

For the third subtask, we observe that for each item, Dankey Kang should either steal nothing or steal everything. This results in ~2^N~ possible ways of stealing. To check if Fax's Thanksgiving is ruined, we can follow the recipe a lot of times. It is enough to go through all recipes ~M~ times, then check if Fax has item ~1~.

Time Complexity: ~\mathcal{O}(MN 2^N)~, which simplifies to ~\mathcal{O}(N^2 2^N)~

Under what conditions would Fax's Thanksgiving be ruined? First, we have a wish list, which is initially the set ~\{1\}~. If we do not have an item in the wish list, then there are two cases to consider:

• If this item is a parent, then we remove it from the wish list. Afterwards, we add all of its required items to the wish list.
• If this item is a leaf, then Fax's Thanksgiving is ruined.

If the second condition never occurs, then Fax will eventually have the required items in his wish list, and Fax's Thanksgiving is not ruined.

If the second condition occurs, then Fax's Thanksgiving is ruined. The leaf's ancestors must have went through the first condition (i.e. they were in the wish list, but were later removed). In other words, there are no items in the path from item ~1~ to the leaf.

Dankey Kang's strategy is to pick a path from item ~1~ to any leaf, then steal all items in this path. Repeat this for every leaf, and store the best answer. This direct approach is ~\mathcal{O}(N^2)~, which is too slow. There are two common ways of speeding this up to ~\mathcal{O}(N)~.

• Generate an array where ~arr[x]~ stores the number of items in the path from item ~1~ to item ~x~. This is similar to a prefix sum. Afterwards, find the leaf that minimizes ~arr[leaf]~.
• Define ~f(x)~ to be the minimal number of items stolen such that Fax cannot have item ~x~. This is the most natural way of solving this problem, and the answer is ~f(1)~.

Note: The answer can be up to ~2.1~ billion, which fits in a 32-bit signed integer. Make sure that your code can handle this number.

Time Complexity: ~\mathcal{O}(N)~