Dish Of Life
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef wants to serve mankind by making people immortal by preparing a dish, a dish of life - a dish with the best taste in the universe, one with the smell and splash of fresh water flowing down the springs of the mountain, one with the smell of the best lily flowers of the garden, one that has contained the very essence of life in a real sense.
This dish will contain K ingredients that are found only in remote islands amid mountains. For sake of convenience, we enumerate the ingredients by the integers from 1 to K, both inclusive. There are N islands and each of them offers some ingredients. Chef being a little child did not know how to collect the ingredients for the recipe. He went to all the islands and bought all the ingredients offered in each island. Could he possibly have saved some time by skipping some island? If it was not possible for Chef to collect the required ingredients (i.e. all the K ingredients), output "sad". If it was possible for him to skip some islands, output "some", otherwise output "all".
First line of the input contains an integer T denoting number of test cases. The description of T test cases follow.
The first line of each test case contains two space separated integers N, K.
The i-th of the next lines will contain first an integer Pi, denoting the number of ingredients grown in the i-th island, followed by Pi distinct integers in the range [1, K]. All the integers are space separated.
For each test case, output a single line containing one of the strings "sad", "all" or "some" (without quotes) according to the situation.
- 1 ≤ T ≤ 10
- 1 ≤ N, K ≤ 105
- 1 ≤ Pi ≤ K
- Sum of Pi over all test cases ≤ 106
Subtask #1 (30 points)
- 1 ≤ N, K ≤ 50
Subtask #2 (30 points)
- 1 ≤ K ≤ 50
Subtask #3 (40 points)
- original constraints
Input 3 3 4 3 1 2 3 2 1 3 2 1 2 2 3 3 1 2 3 2 1 3 2 3 2 1 2 2 1 3 Output sad some all
Example 1. The ingredient 4 is not available in any island, so Chef can't make the dish of life. Hence, the answer is "sad".
Example 2. Chef can just go to the first island and collect all the three ingredients required. He does not need to visit the second island. So, the answer is "some".
Example 3. Chef has to visit both the islands in order to obtain all the three ingredients. So, the answer is "all".
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.