# DISHLIFE - Editorial

There are $n$ islands, and $k$ ingredients numbered from $1$ to $k$. Each island contains some ingredients, let ~~$a_i$ ~~${ingredient}_i$ denotes the list of ingredients in $i$-th island. Chef wants to collect these ingredients from these islands. He wants to check ~~whether ~~following cases.
- Whether it is even possible to collect the $k$ required ingredients.
- If yes, then he wants to know whether he will need to visit all the $n$ islands for collecting these ingredients, or he can do it by visiting less than $n$ islands.
You have to identify which of these scenarios is there.
----
Checking whether Chef ~~will need to visit all the islands to ~~can even collect the desired $k$ ingredients ~~is simple. You have to check if all the ingredients from $1$ to $k$ are ~~or not. This is same as checking whether is there some ingredient which is not present in ~~at least one ingredient. ~~any island.
For each ingredient, ~~you ~~we can maintain the number of islands it is ~~present, and ~~present in. let $cnt[i]$ denote the number of islands in which the ingredient $i$ is present.
We can check whether there is some ingredient whose ~~cnt is zero.
~~$cnt$ value is zero or not.
int cnt[K + 1]
for i = 1 to n:
for j = 0 to ingredints[i].size():
x = ingredients[i][j]
cnt[x] += 1;
for i = 1 to k:
if (cnt[i] == 0):
// It means that ingredient i is not present in any of the islands.
----
Now, we know that it is possible to collect the $k$ ingredient. Now we should find whether Chef will need ~~to check whether we require ~~to visit all the $n$ islands ~~to collect the $k$ ingredients. So, the idea is that for each ~~for collecting these ingredients or not. If there is a ingredient $i$ which is present only in a single island, ~~we ~~i.e. $cnt[i] = 1$, then you will ~~check that suppose Chef did not ~~have to definitely need to visit this island. Otherwise, you can skip this island, ~~can he still ~~and collect ~~all ~~the ingredients from ~~the ~~remaining ~~$n-1$ islands? If such a island exists, then it will mean Chef does not need to visit all the islands to collect the ingredients. ~~$n - 1$ islands.
// For each island, check if Chef doesn't visit this island, can he still visit collect all the ~~ingredients?
~~ingredients from the remaining islands?
need_to_visit_all = true;
for i = 1 to n:
can_collect_all_ingredient_without_this_island = true;
for j = 0 to ingredints[i].size():
x = ingredients[i][j]
if (cnt[x] == 1):
can_collect_all_ingredient_without_this_island = false
~~
This can ~~ if (can_collect_all_ingredient_without_this_island):
need_to_visit_all = false;
Time complexity of this algorithm will be ~~also be done by checking whether is some ingredient who is present in only one island.
need_to_visit_all_islands = false;
for i = 1 to K:
if cnt[i] == 1:
need_to_visit_all_islands = true~~equal to $\text{ingredient}[1].\text{size}() \, + \, \text{ingredient}[2].\text{size}() + \dots +\text{ingredient}[n].\text{size}()$. For solving the final subtask, we have the constraints over sum that it will not exceed $10^6$. Hence, it will take around $10^6$ operations for answering each test case.