{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere are N people living on Lying Island. Some of them are good guys, while others are bad.\r\n\u003c/p\u003e\u003cp\u003eIt is known that good guys are always telling truths, while bad guys may be telling either truths or lies.\u003c/p\u003e\u003cp\u003eOne day, an investigator came to Lying Island. He wondered how many good guys are there on the island. So he conducted an investigation.\u003c/p\u003e\u003cp\u003ePeople on the island are numbered from 1 to N. When the investigator was interviewing person i, he showed the islander the information about at most K people numbered from max{i-K,1} to (i-1).\u003c/p\u003e\u003cp\u003eSometimes, the i-th islander would say, \"Oh, person x is a good(bad) guy.\"\u003c/p\u003e\u003cp\u003eBut sometimes, the i-th islander would mince his words, \"Eh, if person x is a good(bad) guy, person y is a good(bad) guy.\"\u003c/p\u003e\u003cp\u003eOf course, x and y is less than i but no less than (i-K), because person i only saw the information of that at most K islanders.\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003eThe investigator does not think he can infer exactly how many good guys on the island from these words, but he feels that he can figure out how many good guys at most on the island. Can you help him?\u003c/p\u003e\u003cp\u003e\u003cbr\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (1 \u0026lt;\u003d T \u0026lt;\u003d 50), indicating the number of test cases.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tFor each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe first line contains two integers N and K (0 \u0026lt;\u003d N \u0026lt;\u003d 5000,1 \u0026lt;\u003d K \u0026lt;\u003d 10).\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThen (N-1) lines follow, each line contains a string, indicating the sentences said by person 2 to person N. Each sentence is in one of the following formats:\u003cbr\u003e\t\t\t1. Person i: Person x is a good guy.\u003cbr\u003e\t\t\t2. Person i: Person x is a bad guy.\u003cbr\u003e\t\t\t3. Person i: If person x is a good guy, person y is a good guy.\u003cbr\u003e\t\t\t4. Person i: If person x is a bad guy, person y is a bad guy.\u003cbr\u003e\t\t\tIt is guaranteed that in each sentence, max{1,i-K} \u0026lt;\u003d x,y \u0026lt; i and x ≠ y."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one integer on a single line, indicating the number of good guys at most on the island."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n7 2\r\nPerson 2: Person 1 is a good guy.\r\nPerson 3: Person 2 is a bad guy.\r\nPerson 4: If person 3 is a good guy, person 2 is a good guy.\r\nPerson 5: If person 4 is a good guy, person 3 is a bad guy.\r\nPerson 6: If person 5 is a bad guy, person 4 is a good guy.\r\nPerson 7: If person 6 is a bad guy, person 5 is a bad guy.\r\n7 4\r\nPerson 2: Person 1 is a bad guy.\r\nPerson 3: Person 2 is a bad guy.\r\nPerson 4: If person 3 is a good guy, person 1 is a bad guy.\r\nPerson 5: Person 2 is a bad guy.\r\nPerson 6: If person 4 is a good guy, person 2 is a bad guy.\r\nPerson 7: Person 6 is a bad guy.\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"For the first test case, person 3 is a bad guy, and others are good.\u003cbr\u003e\t\t\tPerson 1: Person 1 said nothing, he is a good guy.\u003cbr\u003e\t\t\tPerson 2: Person 1 is indeed a good guy, and person 2 is saying the truth.\u003cbr\u003e\t\t\tPerson 3: Person 2 is not a bad guy, and person 3 is lying.\u003cbr\u003e\t\t\tPerson 4: Person 3 is not a good guy, so the prerequisite does not met. Person 4 is saying the truth.\u003cbr\u003e\t\t\tPerson 5: Person 4 is indeed a good guy and person 3 is indeed a bad guy. Person 5 is saying the truth.\u003cbr\u003e\t\t\tPerson 6: Person 5 is a good guy. Person 6 is saying the truth.\u003cbr\u003e\t\t\tPerson 7: Person 6 is a good guy. Person 7 is saying the truth."}}]}