{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\nh1,h2,h3,h4,h5,h6{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eIn a large organization, everyone knows a lot of colleagues. However, friendship relations are kept with only a few of them, to whom news are told.\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eSuppose that whenever an employee knows of a piece of news, he tells it to all his friends on the following day. So, on the first day, the source of the information tells it to his friends; on the second day, the source\u0026#39;s friends tell it to their friends; on the third day, the friends of the source\u0026#39;s friends\u0026#39; tell it to their friends; and so on.\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eThe goal is to determine: \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoListBullet\"\u003e\r\n\u003c!--[if !supportLists]--\u003e\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"FONT-FAMILY:\r\nSymbol;mso-ansi-language:\r\nEN-GB;mso-fareast-font-family:\r\nSymbol;mso-bidi-font-family:\r\nSymbol\"\u003e\u003cspan style\u003d\"mso-list:Ignore\"\u003e\u0026middot;\u003cspan style\u003d\"FONT:7pt \u0027Times New Roman\u0027\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e \u003c/span\u003e\u003c!--[endif]--\u003e\u003ci\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:\r\nEN-GB\"\u003ethe maximum daily boom size\u003c/span\u003e\u003c/i\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:\r\nEN-GB\"\u003e, which is the largest number of employees that, on a single day, hear the piece of news for the first time; and \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoListBullet\"\u003e\r\n\u003c!--[if !supportLists]--\u003e\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"FONT-FAMILY:\r\nSymbol;mso-ansi-language:\r\nEN-GB;mso-fareast-font-family:\r\nSymbol;mso-bidi-font-family:\r\nSymbol\"\u003e\u003cspan style\u003d\"mso-list:Ignore\"\u003e\u0026middot;\u003cspan style\u003d\"FONT:7pt \u0027Times New Roman\u0027\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e \u003c/span\u003e\u003c!--[endif]--\u003e\u003cspan class\u003d\"GramE\"\u003e\u003ci\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003ethe\u003c/span\u003e\u003c/i\u003e\u003c/span\u003e\u003ci\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e first boom day\u003c/span\u003e\u003c/i\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e, which is the first day on which the maximum daily boom size occurs. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003ch2\u003e\r\n\t\t\u003cspan style\u003d\"COLOR:#006000\"\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eProblem\u003c/span\u003e \u003co:p\u003e\u003c/o:p\u003e \u003c/span\u003e\u003c/h2\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eWrite a program that, given the friendship relations between the employees and the source of a piece of news, computes the maximum daily boom size and the first boom day of that information spreading process. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003ch2\u003e\r\n\t\t\u003cspan style\u003d\"COLOR:#006000\"\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eInput\u003c/span\u003e \u003co:p\u003e\u003c/o:p\u003e \u003c/span\u003e\u003c/h2\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eThe first line of the input contains the number \u003ci\u003eE\u003c/i\u003e of employees (1\u003ci\u003e \u003c/i\u003e\u0026lt;\u003d\u003ci\u003eE \u003c/i\u003e\u0026lt;\u003d2500). Employees are numbered from 0 to \u003ci\u003eE\u003c/i\u003e-1. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eEach of the following \u003ci\u003eE\u003c/i\u003e lines specifies the set of friends of an employee\u0026#39;s (from employee 0 to employee \u003ci\u003eE\u003c/i\u003e-1). A set of friends contains the number of friends \u003ci\u003eN\u003c/i\u003e (0\u003ci\u003e \u003c/i\u003e\u0026lt;\u003d\u003ci\u003eN \u003c/i\u003e\u0026lt;15), followed by \u003ci\u003eN\u003c/i\u003e distinct integers representing the employee\u0026#39;s friends. All integers are separated by a single space. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eThe next line contains an integer \u003ci\u003eT\u003c/i\u003e (1\u003ci\u003e \u003c/i\u003e\u0026lt;\u003d\u003ci\u003eT \u003c/i\u003e\u0026lt;60), which is the number of test cases. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eEach of the following \u003ci\u003eT\u003c/i\u003e lines contains an employee, which represents the (unique) source of the piece of news in the test case. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003ch2\u003e\r\n\t\t\u003cspan style\u003d\"COLOR:#006000\"\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eOutput\u003c/span\u003e \u003co:p\u003e\u003c/o:p\u003e \u003c/span\u003e\u003c/h2\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eThe output consists of \u003ci\u003eT\u003c/i\u003e lines, one for each test case. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eIf no employee (but the source) hears the piece of news, the output line contains the integer \u003c/span\u003e\u003ctt\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"FONT-SIZE:10pt;mso-ansi-language:EN-GB\"\u003e0\u003c/span\u003e\u003c/tt\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eOtherwise, the output line contains two integers, \u003ci\u003eM\u003c/i\u003e and \u003ci\u003eD\u003c/i\u003e, separated by a single space, where \u003ci\u003eM\u003c/i\u003e is the maximum daily boom size and \u003ci\u003eD\u003c/i\u003e is the first boom day. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003ch2\u003e\r\n\t\t\u003cspan style\u003d\"COLOR:#006000\"\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eSample Input\u003c/span\u003e \u003co:p\u003e\u003c/o:p\u003e \u003c/span\u003e\u003c/h2\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e6\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e2 1 2\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e2 3 4\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e3 0 4 5\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e1 4\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e0\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e2 0 2\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e3\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e0\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e4\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e5\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003ch2 style\u003d\"tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt\"\u003e\r\n\t\t\u003cspan style\u003d\"COLOR:#006000\"\u003e\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eSample Output\u003c/span\u003e \u003co:p\u003e\u003c/o:p\u003e \u003c/span\u003e\u003c/h2\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e3 2\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e0\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cpre\u003e\r\n\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003e2 1\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/pre\u003e\r\n\t\u003cdiv align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"TEXT-ALIGN:center;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt\"\u003e\r\n\t\t\u003chr align\u003d\"center\" size\u003d\"2\" width\u003d\"100%\" /\u003e\r\n\t\u003c/div\u003e\r\n\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"TEXT-ALIGN:center;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt\"\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"FONT-SIZE:13.5pt;mso-ansi-language:EN-GB\"\u003e\u003cspan data-scayt_word\u003d\"MIUP\u00272004\" data-scaytid\u003d\"1\"\u003eMIUP\u0026#39;2004\u003c/span\u003e: Fourth Portuguese National Programming Contest\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cdiv align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"TEXT-ALIGN:center;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt\"\u003e\r\n\t\t\u003chr align\u003d\"center\" size\u003d\"2\" width\u003d\"100%\" /\u003e\r\n\t\u003c/div\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt\"\u003e\r\n\t\t\u003cspan lang\u003d\"EN-GB\" style\u003d\"mso-ansi-language:EN-GB\"\u003eProgram setter: \u003cspan data-scayt_word\u003d\"Margarida\" data-scaytid\u003d\"2\"\u003eMargarida\u003c/span\u003e \u003cspan data-scayt_word\u003d\"Mamede\" data-scaytid\u003d\"3\"\u003eMamede\u003c/span\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\u003c/div\u003e"}}]}