{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003clink href\u003d\"css/light_oj.css\" rel\u003d\"stylesheet\" type\u003d\"text/css\" /\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\u0026quot;... so forward this to ten other people, to prove that you believe the emperor has new clothes.\u0026quot;\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tAren\u0026#39;t those sorts of emails annoying?\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tMartians get those sorts of emails too, but they have an innovative way of dealing with them. Instead of just forwarding them \u003cspan data-scayt_word\u003d\"willy-nilly\" data-scaytid\u003d\"1\"\u003ewilly-nilly\u003c/span\u003e, or not at all, they each pick one other person they know to email those things to every time - exactly one, no less, no more (and never themselves). Now, the Martian clan chieftain wants to get an email to start going around, but he stubbornly only wants to send one email. Being the chieftain, he managed to find out who forwards emails to whom, and he wants to know: which Martian should he send it to maximize the number of Martians that see it?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e\u0026le; 20)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tEach case starts with a line containing an integer \u003cb\u003eN (2 \u0026le; N \u0026le; 50000)\u003c/b\u003e denoting the number of Martians in the community. Each of the next \u003cb\u003eN\u003c/b\u003e lines contains two integers: \u003cb\u003eu v (1 \u0026le; u, v \u0026le; N, u \u0026ne; v)\u003c/b\u003e meaning that Martian \u003cb\u003eu\u003c/b\u003e forwards email to Martian \u003cb\u003ev\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tFor each case, print the case number and an integer \u003cb\u003em\u003c/b\u003e, where \u003cb\u003em\u003c/b\u003e is the Martian that the chieftain should send the initial email to. If there is more than one correct answer, output the smallest number.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 2\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 1\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e4\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 2\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 1\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 2\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e5\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 2\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 1\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e5 3\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3 4\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e4 5\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 1: 1\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: 4\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNoSpacing\"\u003e\r\n\t\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 3: 3\u003c/span\u003e\u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tStrongly connected component and graph reconstruct and dp\u003c/p\u003e"}}]}