Indian National Olympiad in Informatics

Related:

Online Programming Contest, 10-11 June 2006

IARCS home > OLYMPIAD

Basic Division

Problem 2: Rearranging Columns, (K Narayan Kumar, CMI)

You will be given to M ×N arrays of integers. The aim is to see if one can be "transformed" into the other in a sequence of steps. In each step, you are allowed to exchange any pair of columns.

For instance, Here are two matrices 3 ×5 matrices:

 2  8  9 10 56
11 12  3  9  5
 3  9 27 16 12


56  2  9 10  8
 5 11  3  9 12
12  3 27 16  9

In this case, the answer is yes. You can first interchange the first and last columns of the second matrix and then the first and second columns to get the first matrix.

Input format

The first line contains two integers M and N giving the number of rows and coloumns in the two matrices. This is followed by 2M lines, each containing N integers giving the elements of the two matrices.

Output format

A single line with YES if it is possible and NO otherwise.

Note: In this task, test inputs will be arranged in groups and marks will be assigned for groups of test inputs rather than to each individual test input. For example, one mark may be assigned for a group of three test inputs. This means that to score that one mark your program must run correctly on all three test inputs in the group. Thus, blindly printing YES (or NO) is not likely to score many marks.

Test data

You may assume that 1 ≤ M ≤ > 100. You may also assume that 1 ≤ N ≤ 500.

Example

We now illustrate the input and output formats using the above example.

Sample input

3 5
2 8 9 10 56
11 12 3 9 5
3 9 27 16 12
56 2 9 10 8
5 11 3 9 12
12 3 27 16 9

Sample output

YES