There are n machines placing toppings onto the pizza. There are only two types of toppings -- cheese(C) and ham(H). For machine Mi, it would have at most two options: (i) stack up a piece of cheese on the current pizza, then send it to another machine Mc(i), or (ii) stack up a piece of ham on the current pizza, then send it to another machine Mh(i). A pizza can be sent in or taken out from any machine.
You are interested in the robustness of these n machines. Please write a program to detect if, for any sequence of cheese and hams, there is a way to generate such pizza.
Warn: 本題有 specialjudge
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
For each test case, first line contains an integer n (1<= n<= 50) indicating the number of machines. Each of the next n lines contains two integers c(i), h(i). The number -1 means that it is impossible for this machine to put that kind of toppings.
For each test case, output Yes if for all sequence there exist some ways to generate it. Otherwise, output No then followed by any string consisting of C and H that denotes a pizza which cannot be generated.
The input is guaranteed that, for any No answer, there is a cannot-be-generated pizza/string whose length will not exceed 1357. Thus, your answer should also have length at most 1357.
3 2 1 2 1 2 2 1 -1 -1 1 1 1 1
Yes No HH Yes
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|