{"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:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/900dfb988c343744fb31b3b3af0062ff?v\u003d1715579068\" alt\u003d\"/problems/abandonedanimal/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eYour little sister has been a big help today: she went\n into town to do all the groceries! During this grand voyage,\n she was accompanied by her fluffy friend, Mr.\u0026nbsp;Fluffynose\n the Stuffed Animal. However, after her return, it seems that\n she has left him somewhere along the route! This is devastating\n news for your little sister, and as she won’t stop crying about\n it, you decide to retrace her steps through town.\n\n \u003cp\u003eYou know that your sister will hold on to her beloved\n Fluffynose whenever possible, so the only time she could’ve\n lost it is when she grabbed an item on her shopping list. So,\n all you have to do is figure out at what store she bought what,\n and then you’ll reunite her with her counterpart in no time!\n However, you soon find out that this isn’t quite as easy as you\n thought: she went to a lot of stores, and although she knows\n the names of the stores she went to and the order in which she\n visited them, she does not recall what she bought at each store\n (it could have been nothing!). It would take a lot of time to\n blindly search all the stores for all these items. As you have\n better things to do today, like solving programming problems,\n you want to spend as little time on this retrieval as possible.\n Therefore, you want to know exactly which items your sister\n bought at each store before you start your search.\u003c/p\u003e\n\n \u003cp\u003eFor this you have two pieces of information: firstly you\n know the inventory of all stores your sister went to. Secondly,\n you know exactly in what order she purchased the groceries, as\n she has very carefully stacked all items into her bag. You\n decide to number the stores your sister visited according to\n the order in which she visited them. Given this information,\n you want to decide whether you know for sure where she bought\n every item so you can retrace her steps as efficiently as\n possible.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input starts with a line with a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq N \\leq 100{,}000$\u003c/span\u003e,\n the number of supermarkets in town. Then follows a line with an\n integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N\\leq K \\leq\n 100{,}000$\u003c/span\u003e, after which \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e lines follow with a\n space-separated integer \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e (between \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$N-1$\u003c/span\u003e) and a string \u003cspan class\u003d\"tex2jax_process\"\u003e$S$\u003c/span\u003e (consisting of only lowercase\n letters, at most \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e),\n denoting that item \u003cspan class\u003d\"tex2jax_process\"\u003e$S$\u003c/span\u003e is\n available at the \u003cspan class\u003d\"tex2jax_process\"\u003e$i^\\text\n {th}$\u003c/span\u003e store that your sister visited. It is guaranteed\n that every store has at least one item, every item is available\n at at least one store, and that every item occurs at most once\n at every store.\u003c/p\u003e\n\n \u003cp\u003eThe second part of the input contains the list of items your\n sister bought, in order of purchase. It starts with a line with\n an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$M\\leq K$\u003c/span\u003e, the\n number of items your sister has bought. Then follow\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e lines, each with\n string \u003cspan class\u003d\"tex2jax_process\"\u003e$T$\u003c/span\u003e, denoting the\n name of the item your sister bought. The items are given in the\n order she purchased them in. All items that your sister has\n bought are unique.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput “\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003e\" if there is no\n path through the stores that matches your sister’s description.\n Output “\u003ctt class\u003d\"ttfamily\"\u003eunique\u003c/tt\u003e\" if there is exactly\n one path through the stores that matches. Output “\u003ctt class\u003d\"ttfamily\"\u003eambiguous\u003c/tt\u003e\" if there are multiple possible\n paths.\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\u003e3\n3\n0 chocolate\n1 icecream\n2 cookies\n3\nchocolate\ncookies\nicecream\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\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\u003e3\n4\n0 chocolate\n1 icecream\n2 cookies\n2 chocolate\n3\nchocolate\nicecream\ncookies\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eunique\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 3\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\u003e3\n10\n0 tomatoes\n0 cucumber\n1 tomatoes\n2 tomatoes\n2 cucumber\n1 mustard\n0 salt\n2 salad\n2 salt\n2 mustard\n5\ntomatoes\ncucumber\nsalad\nmustard\nsalt\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eambiguous\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}