All submissions for this problem are available.
Help! A brush fire has started near your house and you are the only one who can help extinguish it. The only tool you have at your disposal is a single fireproof barrier that can protect one bush at a time, provided the bush has not yet caught fire already. For simplicity, we will assume the flames spread according to the following discrete time model.
Initially, a single bush, say s, is on fire. You choose a bush, say k, to save. The flames then leap from s to every bush near s with the exception of bush k if it was near s. Say these new burning bushes form a set B. Bush s is then reduced to ashes and will never burn again. Now that the bushes in B are on fire, you may move the protective barrier from bush k to some other bush k'. The flames leap from bushes in B to every bush that has not yet burned (i.e. not s or in B) and is close enough to some bush in B except, perhaps, bush k'. Say this new set of burning bushes is B'.
The bushes in set B are reduced to ashes and will never burn again. Now, you may move the protective barrier from k' to another bush to protect it from the flames that will spread from bushes in B' and so on. This process repeats until there are no more bushes on fire.
The bushes are arranged in a peculiar manner. Before the fire started, each bush was close enough to spread a fire to at most three other bushes. Moreover, the bush that was initially on fire is actually close enough to only at most two other bushes. It is understood that for any two bushes A and B, if bush A is close enough to bush B then bush B is also close enough to bush A. Finally, the graph underlying the "close enough" relation has no cycles.
For whatever reason, some of the bushes hold some sentimental value to you. For this reason, you want to save all of these bushes.
The first line of the input contains a single integer T ≤ 40 indicating the number of test cases that will follow. Each test case begins with three integers n, s, and t satisfying 1 ≤ n ≤ 10,000 and both s and t are between 1 and n. Here, n is the number of bushes (indexed from 1 to n), s is the index of the bush that is initially on fire, and t is the number of bushes you want to save.
Following this, there are n lines describing the "close enough" relation. The i'th line starts with an integer 0 ≤ ci ≤ 3 meaning bush i is close enough to ci other bushes. The remaining ci integers on this line are the indices of the bushes that bush i is close to. As mentioned earlier, the input will be such that if bush i is close enough to bush j, then bush j is also close enough to bush i. Finally, we also guarantee that cs ≤ 2.
The last line of input for each test case consists of t distinct integers between 1 and n. These correspond to indices of bushes you want to save.
Test cases are separated by a single blank line (including a blank line preceding the first test case).
For each test case, you are to output a single line consisting of either "yes" or "no", depending on whether or not it is possible to save all of the indicated bushes.
Input: 3 3 1 2 2 2 3 1 1 1 1 2 3 3 1 1 2 2 3 1 1 1 1 2 7 1 3 2 2 3 3 1 4 5 3 1 6 7 1 2 1 2 1 3 1 3 4 5 7 Output: no yes yes
|Tags||easy, friggstad, sept10|
|Time Limit:||0.794 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.