{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nA palidrome craftsperson starts to work in the early morning, \nwith the clear air allowing him to polish up his palindromes.\n\u003c/p\u003e\n\n\u003cp\u003e\nOn this morning, he is making his pieces to submit to the International Contest for Palindrome Craftspeople.\n\u003c/p\u003e\n\n\u003cp\u003e\nBy the way, in order to make palindromes, he uses a special dictionary which contains a set of words and a set of ordered pairs of the words.\nAny words and any ordered pairs of consecutive words in his palindromes must appear in the dictionary.\n\u003c/p\u003e\n\n\u003cp\u003e\nWe already have his dictionary, so let\u0027s estimate how long a palindrome he can make.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe first line in the data set consists of two integers \u003cvar\u003eN\u003c/var\u003e (\u003cvar\u003e1 \\leq N \\leq 100\u003c/var\u003e) and \u003cvar\u003eM\u003c/var\u003e (\u003cvar\u003e0 \\leq M \\leq 1\\,000\u003c/var\u003e).\n\u003cvar\u003eN\u003c/var\u003e describes the number of words in the dictionary and \u003cvar\u003eM\u003c/var\u003e describes the number of ordered pairs of words.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe following \u003cvar\u003eN\u003c/var\u003e lines describe the words he can use.\nThe \u003cvar\u003ei\u003c/var\u003e-th line (\u003cvar\u003e1\u003c/var\u003e-based) contains the word \u003cvar\u003ei\u003c/var\u003e, which consists of only lower-case letters and whose length is between \u003cvar\u003e1\u003c/var\u003e and \u003cvar\u003e10\u003c/var\u003e, inclusive.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe following \u003cvar\u003eM\u003c/var\u003e lines describe the ordered pairs of consecutive words he can use.\nThe \u003cvar\u003ej\u003c/var\u003e-th line (\u003cvar\u003e1\u003c/var\u003e-based) contains two integers \u003cvar\u003eX_j\u003c/var\u003e and \u003cvar\u003eY_j\u003c/var\u003e (\u003cvar\u003e1 \\leq X_j, Y_j \\leq N\u003c/var\u003e).\n\u003cvar\u003eX_j\u003c/var\u003e describes the (\u003cvar\u003e1\u003c/var\u003e-based) index of the former word in the palindrome and \u003cvar\u003eY_j\u003c/var\u003e describes that of the latter word.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nPrint the maximal length of the possible palindrome in a line.\nIf he can make no palidromes, print \"0\".\nIf he can make arbitrary long palindromes, print \"-1\". \n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e2 2\nab\nba\n1 1\n1 2\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e4\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e2 2\nab\nba\n1 1\n2 2\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e0\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e2 2\nab\na\n1 1\n1 2\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e-1\n\u003c/pre\u003e\n"}}]}