Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Love Letter

By Nafis_Shhriar · Limits 1s, 512 MB

Mr. A has finally found the love of his life. Being a love expert Mr. P has given Mr. A an idea to write a love letter. But he is very weak in this matter. So he took help from his friends. He has 2×N2 \times N friends. Each friend has given him one romantic sentence and using all those sentences Mr. A will write a love letter.

Each sentence contains only lower case alphabet (‘a’- ‘z’) and space. The height of each character is 1 and the width of each character is also 1.

But Mr. A is very busy person, So Mr. A has given me the duty to arrange the sentences and make a love letter. He has also given me an N×MN \times M size paper. Now I have to write all the 2×N2 \times N sentences in that paper. But Mr. P has advised me not to write more than two sentences in a row and write in only one side of the paper. He also advised me not to write any sentence using more than one row. So, in order to fit the sentences, I will remove all the spaces and also I will not use any space between two lines.

Now I'm in a dangerous situation, if I refuse to do this work Mr. A will break my legs but if I do the work and something goes wrong he will break my legs too. So I've decided to do this work and hide for a few days. As I'm busy packing my bag i want you to do a job for me.

You will be given N and M, the height and width of the paper, and 2×N2 \times N sentences. You will have to tell me can I write all the sentences in that paper in any order or not.

Input

The first line of the input set will contain two integers NN and MM (1N,M1000 1 \le N, M \le 1000).

The next 2×N2 \times N lines will contain a sentence each, not containing more than 1000 characters.

Output

If I can write all these sentences in the paper in any order, output YES\texttt{YES} and if I can’t output NO\texttt{NO}.

Samples

InputOutput
2 6
a a a
b b b
c c c
d d d
YES
InputOutput
2 28
akasata meg ura
dakta laga sada
bondu amar balobasay
nai kuno kada
NO

Discussion

Statistics


88% Solution Ratio

abcdef123Earliest, 9M ago

abcdef123Fastest, 0.0s

ashadullaharifLightest, 0 B

mdvirusShortest, 471B

Submit

Login to submit