### PROBLEM LINK

### DIFFICULTY

simple

### PREREQUISITES

general programming skills

### PROBLEM

There are n islands, and k ingredients numbered from 1 to k. Each island contains some ingredients, let {ingredient}_i denotes the list of ingredients in i-th island. Chef wants to collect these ingredients from these islands. He wants to check 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 can even collect the desired k ingredients or not. This is same as checking whether is there some ingredient which is not present in any island.

For each ingredient, we can maintain the number of islands it is present in. let cnt* denote the number of islands in which the ingredient i is present.

We can check whether there is some ingredient whose cnt value is zero or not.

```
int cnt[K + 1]
for i = 1 to n:
for j = 0 to ingredients*.size():
x = ingredients*[j]
cnt[x] += 1;
for i = 1 to k:
if (cnt* == 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 visit all the n islands for collecting these ingredients or not. If there is a ingredient i which is present only in a single island, i.e. cnt* = 1, then you will have to definitely need to visit this island. Otherwise, you can skip this island, and collect the ingredients from remaining n - 1 islands.

```
// For each island, check if Chef doesn't visit this island, can he still visit collect all the 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 ingredients*.size():
x = ingredients*[j]
if (cnt[x] == 1):
can_collect_all_ingredient_without_this_island = false
if (can_collect_all_ingredient_without_this_island):
need_to_visit_all = false;
```

Time complexity of this algorithm will be equal to ext{ingredient}[1]. ext{size}() \, + \, ext{ingredient}[2]. ext{size}() + \dots + ext{ingredient}[n]. ext{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.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.