{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e 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","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp style\u003d\"text-align: left;\"\u003eYou are given a board of order m×n full of coloured blocks.\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: center;\"\u003e\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/d66ec83a85f7db61ecc2b7dcacc90af5?v\u003d1725205314\" alt\u003d\"\" width\u003d\"267\" height\u003d\"291\"\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e\u003cbr\u003eAt each move, you have to select a block of any colour which has atleast one of it\u0027s immediate neighbours of same colour. If you select a block, all the connected blocks(not just the immediate neighbours) of same colour gets destroyed. A block is connected to all the blocks that share an edge with it. Any block will fall directly down if there is no block immediately below it. If a complete column becomes empty, you must either push all the columns to it\u0027s left once in the right side or push all the columns to it\u0027s right once in the left side(These pushes are not considered as a moves. At each move, you will destroy more than one block).\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e\u003cbr\u003eYou will win the game if the remaining number of blocks becomes zero after making\u0026nbsp; the moves. Find the minimum number of moves to win the game. If it is impossible to win the game, print -1.\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eFor better understanding of gameplay you may have a look at this \u003ca href\u003d\"https://www.youtube.com/watch?v\u003dP2-mO3K04KQ\"\u003evideo\u003c/a\u003e. (optional)\u003cbr\u003e\u003cbr\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eThe first line consists of an integer t, the number of test cases. For each test case the first line consists of two integers m, n the number of rows and columns respectively followed by the matrix representing the coloured blocks. Colour[i][j] contains any character between \u0027a\u0027 and \u0027e\u0027 inclusive.\u003cbr\u003e\u003cbr\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eFor each test case print the minimum number of moves to win the game. If it is impossible to win, print -1.\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e\u003cbr\u003e\u003cstrong\u003eInput Constraints:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e1\u0026lt;\u003dt\u0026lt;\u003d10\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e1\u0026lt;\u003dm,n\u0026lt;\u003d8\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e\u0027a\u0027\u0026lt;\u003dColour[i][j]\u0026lt;\u003d\u0027e\u0027\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e\u003cstrong\u003eSample Input:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e2\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e5 5\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eaaaba\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eaaaba\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eaaaba\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eaaaba\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eaaaba\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e5 5\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003ebbbbb\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003ebaabb\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003ebbbab\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003ebbbaa\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003eaabab\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e\u003cstrong\u003eSample Output:\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e2\u003c/p\u003e\r\n\u003cp style\u003d\"text-align: left;\"\u003e3\u003c/p\u003e\n\u003c/div\u003e"}}]}