{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section 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\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cstyle\u003e\r\n #nck {\r\n width: 30px;\r\n height: auto;\r\n }\r\n\u003c/style\u003e\r\n\r\n\u003cp\u003eShik\u0027s job is very boring. At day \u003cvar\u003e\\(0\\)\u003c/var\u003e, his boss gives him a string \u003cvar\u003e\\(S_0\\)\u003c/var\u003e of length \u003cvar\u003e\\(N\\)\u003c/var\u003e which consists of only lowercase English letters. In the \u003cvar\u003e\\(i\\)\u003c/var\u003e-th day after day \u003cvar\u003e\\(0\\)\u003c/var\u003e, Shik\u0027s job is to copy the string \u003cvar\u003e\\(S_{i-1}\\)\u003c/var\u003e to a string \u003cvar\u003e\\(S_i\\)\u003c/var\u003e. We denote the \u003cvar\u003e\\(j\\)\u003c/var\u003e-th letter of \u003cvar\u003e\\(S_i\\)\u003c/var\u003e as \u003cvar\u003e\\(S_i[j]\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003cp\u003eShik is inexperienced in this job. In each day, when he is copying letters one by one from the first letter to the last letter, he would make mistakes. That is, he sometimes accidentally writes down the same letter that he wrote previously instead of the correct one. More specifically, \u003cvar\u003e\\(S_i[j]\\)\u003c/var\u003e is equal to either \u003cvar\u003e\\(S_{i-1}[j]\\)\u003c/var\u003e or \u003cvar\u003e\\(S_{i}[j-1]\\)\u003c/var\u003e. (Note that \u003cvar\u003e\\(S_i[1]\\)\u003c/var\u003e always equals to \u003cvar\u003e\\(S_{i-1}[1]\\)\u003c/var\u003e.)\u003c/p\u003e\r\n\u003cp\u003eYou are given the string \u003cvar\u003e\\(S_0\\)\u003c/var\u003e and another string \u003cvar\u003e\\(T\\)\u003c/var\u003e.\r\nPlease determine the smallest integer \u003cvar\u003e\\(i\\)\u003c/var\u003e such that \u003cvar\u003e\\(S_i\\)\u003c/var\u003e could be equal to \u003cvar\u003e\\(T\\)\u003c/var\u003e. If no such \u003cvar\u003e\\(i\\)\u003c/var\u003e exists, please print \u003ccode\u003e-1\u003c/code\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq N \\leq 1,000,000\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003eThe lengths of \u003cvar\u003e\\(S_0\\)\u003c/var\u003e and \u003cvar\u003e\\(T\\)\u003c/var\u003e are both \u003cvar\u003e\\(N\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003cli\u003eBoth \u003cvar\u003e\\(S_0\\)\u003c/var\u003e and \u003cvar\u003e\\(T\\)\u003c/var\u003e consist of lowercase English letters.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eThe input is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(S_0\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(T\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003ePrint the smallest integer \u003cvar\u003e\\(i\\)\u003c/var\u003e such that \u003cvar\u003e\\(S_i\\)\u003c/var\u003e could be equal to \u003cvar\u003e\\(T\\)\u003c/var\u003e. If no such \u003cvar\u003e\\(i\\)\u003c/var\u003e exists, print \u003ccode\u003e-1\u003c/code\u003e instead.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e5\r\nabcde\r\naaacc\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003e\u003cvar\u003e\\(S_0\\)\u003c/var\u003e \u003d \u003ccode\u003eabcde\u003c/code\u003e, \u003cvar\u003e\\(S_1\\)\u003c/var\u003e \u003d \u003ccode\u003eaaccc\u003c/code\u003e and \u003cvar\u003e\\(S_2\\)\u003c/var\u003e \u003d \u003ccode\u003eaaacc\u003c/code\u003e is a possible sequence such that \u003cvar\u003e\\(S_2 \u003d T\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e5\r\nabcde\r\nabcde\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\r\nacaa\r\naaca\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 4","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e5\r\nabcde\r\nbbbbb\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}