---{"category_name":"medium","problem_code":"MATBEAUT","problem_name":"Make the Matrix Beautiful","problemComponents":{"constraints":"- $1 \\leq T \\leq 100$\n- $1 \\leq N, M \\leq 50$\n- Each column contains a permutation of the integers $1,\\ldots, N$.","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line contains a single integer $T$ - the number of test cases. Then the test cases follow.\n- The first line of each test case contains two integers $N$ and $M$.\n- The next $N$ lines have $M$ integers each. The $j$-th integer in the $i$-th line denotes $A[i][j]$","inputFormatState":true,"outputFormat":"For each test case:\n\n- If it is possible to make the matrix beautiful:\n - Print the number of operations you perform in a new line. This number has to be less than or equal to $(N+3) \\cdot (M+3)$.\n - For each operation print four integers: $x_1$, $y_1$, $x_2$, $y_2$ in a new line. \n- If it is not possible to make the matrix beautiful:\n - Print $-1$ in a new line.\n\nIf there are multiple ways to make the matrix beautiful with at most $(N+3) \\cdot (M+3)$ operations, you may print any of them.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"2\n3 3\n1 1 1\n2 3 3\n3 2 2\n3 3\n1 1 1\n2 3 2\n3 2 3","output":"1\n2 2 3 3\n-1","explanation":"- For the first test case, we can swap $A[2][2], A[3][2]$ and swap $A[2][3],A[3][3]$ to make the matrix beautiful.\n- For the second test case it is not possible to make the matrix beautiful.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/9-CEWG5Ed2A","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"smarth297","problem_tester":"","date_added":"25-07-2021","tags":{"0":"constructive","1":"cook131","2":"matrices","3":"medium","4":"smarth297"},"problem_difficulty_level":"Medium","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/MATBEAUT","time":{"view_start_date":1627492504,"submit_start_date":1627492504,"visible_start_date":1627492504,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=MATBEAUT","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK131/mandarin/MATBEAUT.pdf), [Russian](https://www.codechef.com/download/translated/COOK131/russian/MATBEAUT.pdf), [Vietnamese](https://www.codechef.com/download/translated/COOK131/vietnamese/MATBEAUT.pdf) and [Bengali](https://www.codechef.com/download/translated/COOK131/bengali/MATBEAUT.pdf) as well.You are given an $N \times M$ matrix where each element of the matrix consists of an integer color. Let $A[i][j]$ be the color on the matrix in the $i$-th row from the top and $j$-th column from the left. You need to make the matrix *beautiful*.By definition, a matrix is *beautiful* if all the elements of the $i$-th row have color $i$.That is, all the elements of the first row have color $1$, all elements of the second row have color $2$, so on.In an operation, you can do the following:- Choose four integers $x_1, y_1, x_2, y_2$ ($1\le x_1, x_2\le N$, $1\le y_1, y_2\le M$, $x_1\ne x_2, y_1\ne y_2$)- Swap the values $A[x_1][y_1]$ and $A[x_2][y_1]$.- Swap the values $A[x_1][y_2]$ and $A[x_2][y_2]$.If you can make the matrix beautiful, then give a sequence of at most $(N+3)\cdot (M+3)$ operations to do so. Otherwise, print $-1$.We have a proof that if it is possible to make the matrix beautiful in a finite number of operations, then it can be done in at most $(N+3)\cdot (M+3)$ operations.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>