{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:23.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/5de84ebf49b715fadd623980f69798dd?v\u003d1715640158\" alt\u003d\"/problems/britishmenu/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eSince you are in Britain, you definitely want to try British\n food. Unfortunately you will only have a single free evening,\n so you decided to try all the food you can get in one run. You\n plan a gigantic meal where you eat one British dish after the\n other. Clearly not every order of dishes is appropriate. For\n example, it is not acceptable to eat Blood Pudding directly\n after Cornish Hevva Cake, but it would be perfectly fine if you\n chose to eat Baked Beans in between.\u003c/p\u003e\n\n \u003cp\u003eYou have compiled a comprehensive list of British dishes.\n For each dish you have also decided which other dishes are fit\n to be eaten directly afterwards. A menu is a sequence of dishes\n such that each dish (except the first) is fit to be eaten\n directly after the previous dish.\u003c/p\u003e\n\n \u003cp\u003eAfter some time studying the list of dishes, you noticed\n something odd: Whenever it is possible to find a menu in which\n a dish occurs twice (for example dishes \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e, then \u003cspan class\u003d\"tex2jax_process\"\u003e$B$\u003c/span\u003e, then \u003cspan class\u003d\"tex2jax_process\"\u003e$C$\u003c/span\u003e, then dish \u003cspan class\u003d\"tex2jax_process\"\u003e$A$\u003c/span\u003e again), there can be at most four\n different types of dishes between the dish that occurred twice\n – excluding that dish itself. For example, it is impossible to\n find a menu like \u003cspan class\u003d\"tex2jax_process\"\u003e$A, B, C, D, E,\n F, A$\u003c/span\u003e, but it may be possible to find menus like\n \u003cspan class\u003d\"tex2jax_process\"\u003e$A, B, C, B, C, B, C, B, C, B,\n A$\u003c/span\u003e or \u003cspan class\u003d\"tex2jax_process\"\u003e$A,B,C,D,E,A,B,C,D,E,A$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eBut who wants to eat the same dish twice anyway? Clearly,\n you want to know how many dishes there can be in a menu without\n repeating any dish!\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n,m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 10^5$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq m \\leq 10^6$\u003c/span\u003e), the number\n of dishes and compatibilities.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines, each\n containing two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq a,b \\leq n$\u003c/span\u003e), indicating\n that you can eat dish \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e immediately after dish\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eDishes are numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e in no particular order, and the\n compatibilities satisfy the constraint described above.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eA single integer indicating the maximum number of courses in\n a menu without repeated dishes.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4 3\n1 2\n2 3\n2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e7 7\n1 2\n2 3\n3 4\n4 5\n5 2\n4 6\n5 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}