{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eJolly Kingdom is a kingdom which is famous for its troops\u0027 power. Jolly Kingdom has N swordsman troops and M archer troops where each troop has his/her own unique fighting style, different with others.\u003c/p\u003e\r\n\u003cp\u003eFor the 10\u003csup\u003eth\u003c/sup\u003e times, an evil witch with her monster troops tries to seize the throne of Jolly Kingdom. According to the information gathered from Jolly Kingdom\u0027s spies, the witch will attack everyday for H days. Each day, the witch will add 1 new monster into her monster troops. This makes enemy\u0027s troops become stronger every day.\u003c/p\u003e\r\n\u003cp\u003eEach monster owned by the witch is strong and almost unbeatable, only the X\u003csub\u003ei\u003c/sub\u003e\u003csup\u003eth\u003c/sup\u003e swordsman troop or the Y\u003csub\u003ei\u003c/sub\u003e\u003csup\u003eth\u003c/sup\u003e archer troop can beat the monster. After the monster has been defeated by Jolly Kingdom\u0027s troop, that monster will take a reset and attack again in the next day.\u003c/p\u003e\r\n\u003cp\u003eTo protect Jolly Kingdom, every day \u003cstrong\u003eall monsters\u003c/strong\u003e have to be defeated, but the cost to send 1 troop is expensive, so the king wants to send minimum number of troops every day such that the sent troops will be able to defeat \u003cstrong\u003eall monsters\u003c/strong\u003e exist on that corresponding day.\u003c/p\u003e\r\n\u003cp\u003eThe king asks you for your help, as a royal advisor, the number of troops the king has to send every day.\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eInput\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003eFirst line consists of 3 integers: N, M, and H (1 ≤ N, M ≤ 1000; 1 ≤ H ≤ N*M) – the number of swordsman troops, archer troops, and days. Each of next H lines contains 2 integers: X\u003csub\u003ei\u003c/sub\u003e and Y\u003csub\u003ei\u003c/sub\u003e (1 ≤ X\u003csub\u003ei\u003c/sub\u003e ≤ N; 1 ≤ Y\u003csub\u003ei\u003c/sub\u003e ≤ M) – the weakness of i\u003csup\u003eth\u003c/sup\u003e monster, i\u003csup\u003eth\u003c/sup\u003e can be defeated by the X\u003csub\u003ei\u003c/sub\u003e\u003csup\u003eth\u003c/sup\u003e swordsman or Y\u003csub\u003ei\u003c/sub\u003e\u003csup\u003eth\u003c/sup\u003e archer.\u003c/p\u003e\r\n\u003cp\u003eThere can\u0027t be 2 monsters with the exact same weakness (there won\u0027t be any monster i and j where X\u003csub\u003ei\u003c/sub\u003e \u003d X\u003csub\u003ej\u003c/sub\u003e and Y\u003csub\u003ei\u003c/sub\u003e \u003d Y\u003csub\u003ej\u003c/sub\u003e for all 1 ≤ i, j ≤ H and i ≠ j).\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eOutput\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003ePrint H lines. Each line contains 1 number represents the answer to the king\u0027s question.\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eSample Tests\u003c/strong\u003e\u003c/p\u003e\r\n\u003c!-- ngRepeat: input in problemDetails.sampleInput track by $index --\u003e \r\n\u003ctable class\u003d\"table table-striped ng-scope\" border\u003d\"0\"\u003e\r\n\u003ctbody\u003e\r\n\u003ctr style\u003d\"background-color: #cccccc;\"\u003e\r\n\u003ctd class\u003d\"tableHeader\"\u003eInput\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003ctr style\u003d\"background-color: #eeeeee;\"\u003e\r\n\u003ctd\u003e\r\n\u003cpre class\u003d\"ng-binding\"\u003e4 4 9\r\n1 1\r\n1 2\r\n1 3\r\n2 1\r\n4 1\r\n3 4\r\n3 3\r\n4 3\r\n4 4\r\n\u003c/pre\u003e\r\n\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003ctr style\u003d\"background-color: #cccccc;\"\u003e\r\n\u003ctd class\u003d\"tableHeader\"\u003eOutput\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003ctr style\u003d\"background-color: #eeeeee;\"\u003e\r\n\u003ctd\u003e\r\n\u003cpre class\u003d\"ng-binding\"\u003e1\r\n1\r\n1\r\n2\r\n2\r\n3\r\n3\r\n4\r\n4\r\n\u003c/pre\u003e\r\n\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003c/tbody\u003e\r\n\u003c/table\u003e\r\n\u003c!-- end ngRepeat: input in problemDetails.sampleInput track by $index --\u003e\r\n\u003cp\u003e\u003cstrong\u003eExplanation for sample case\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp\u003eNotation: { swordsman troop number: monster number(s) defeated } { archer troop number: monster number(s) defeated }\u003cbr\u003e 1\u003csup\u003est\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1} {}\u003cbr\u003e 2\u003csup\u003end\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2} {}\u003cbr\u003e 3\u003csup\u003erd\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3} {}\u003cbr\u003e 4\u003csup\u003eth\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3} {\u003cstrong\u003e1\u003c/strong\u003e: 4}\u003cbr\u003e 5\u003csup\u003eth\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3} {\u003cstrong\u003e1\u003c/strong\u003e: 4 5}\u003cbr\u003e 6\u003csup\u003eth\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3; \u003cstrong\u003e3\u003c/strong\u003e: 6} {\u003cstrong\u003e1\u003c/strong\u003e: 4 5}\u003cbr\u003e 7\u003csup\u003eth\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3; \u003cstrong\u003e3\u003c/strong\u003e: 6 7} {\u003cstrong\u003e1\u003c/strong\u003e: 4 5}\u003cbr\u003e 8\u003csup\u003eth\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3; \u003cstrong\u003e3\u003c/strong\u003e: 6 7; \u003cstrong\u003e4\u003c/strong\u003e: 8} {\u003cstrong\u003e1\u003c/strong\u003e: 4 5}\u003cbr\u003e 9\u003csup\u003eth\u003c/sup\u003e day: {\u003cstrong\u003e1\u003c/strong\u003e: 1 2 3; \u003cstrong\u003e3\u003c/strong\u003e: 6 7; \u003cstrong\u003e4\u003c/strong\u003e: 8 9} {\u003cstrong\u003e1\u003c/strong\u003e: 4 5}\u003c/p\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eInformation\u003c/strong\u003e\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThe constraints above is not typo, N and M can be as large as 1000 (1 Thousand), so H can be as large as 10\u003csup\u003e6\u003c/sup\u003e (1 Million). So this problem has 10× larger constraints than the original one.\u003c/li\u003e\r\n\u003cli\u003eWarning: Large Input/Output files, each file I/O can be as large as 7.5 Megabytes (7.5 MB), cin or cout probably too slow for I/O, it\u0027s recommended to use scanf/printf (I\u0027ve tested it).\u003c/li\u003e\r\n\u003cli\u003eIf you find this problem too hard, you can try this first: \u003ca href\u003d\"https://jollybeeoj.com/problem/view/199\" target\u003d\"_blank\"\u003ehttps://jollybeeoj.com/problem/view/199\u003c/a\u003e\u0026nbsp;original problem with smaller constraints.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eTrivia\u003c/strong\u003e\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThe total size of file I/O in this problem is slightly more than 100 MB, took a while to generate, modify, and upload it. :)\u003c/li\u003e\r\n\u003cli\u003eIf the witch attack Jolly Kingdom everyday for 1 Million days that means the attack took more than 2500 years. :o\u003c/li\u003e\r\n\u003cli\u003eIf I count number of operation in the deepest loop of my algo on worst case input, it will be 671,163,499 operations.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003eCredit \u0026amp; Special thanks\u003c/strong\u003e\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003ca title\u003d\"Sandy Karunia\" href\u003d\"https://id.linkedin.com/in/sandy-karunia-150097a8\" target\u003d\"_blank\"\u003eSandy Karunia\u003c/a\u003e - Developer of \u003ca href\u003d\"https://jollybeeoj.com/\" target\u003d\"_blank\"\u003eJollybee Online Judge\u003c/a\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003ca title\u003d\"Alvin Setiadi\" href\u003d\"https://id.linkedin.com/in/alvin-setiadi-512289aa\" target\u003d\"_blank\"\u003eAlvin Setiadi\u003c/a\u003e - Original problem author\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\n\u003c/div\u003e"}}]}