Testing Sorting Networks

Time limit2sMemory limit512 MB

Summary

Given a layered circuit of N/2 sorters joined by fixed wiring, decide whether every 0-1 input ends up sorted after all stages.

Level: Medium6 of 10
Topics: Sorting, Bit manipulation, Brute force, Simulation
Solved: No attempts yet

Problem

An N sorting network is a circuit that takes N numbers as input and outputs them in sorted order. Mr. Smith is an engineer at a company that sells the circuit in various sizes.

One day the company received an order for N sorting networks. Unfortunately, at that time they had no circuit that handled N numbers. The clerk turned the order down for being out of stock, but the client was in such a hurry that he offered a lot of money to get the circuit within a week. The deal went up to a manager, and she asked Mr. Smith for a way to produce the N sorting networks by the deadline.

He came up with the idea of combining several N/2 sorting networks, because he knew the company had plenty of circuits for N/2 numbers in stock. He designed a new circuit from N/2 sorting networks, but he was not sure whether it really worked as an N sorting network. So he asked you, a colleague, to check whether it was actually an N sorting network.

The circuit he designed consists of several stages. Each stage is made of two N/2 sorting networks, so each stage takes a sequence of N numbers as input and outputs a sequence of N numbers. The 1st through N/2-th inputs of a stage go to one of the N/2 sorting networks, and the (N/2+1)-th through N-th inputs go to the other. Likewise, the first half of a stage's outputs is the output of the first sorting network and the second half is the output of the second, and both are sorted in ascending order. Each output of a stage is connected to exactly one input of the next stage, and no two inputs are connected to the same output line. The input of the last stage is the input of the whole circuit, and the output of the first stage is the output of the whole circuit.

Input

The first line contains a positive even integer N (4 ≤ N ≤ 100) and a positive integer D (1 ≤ D ≤ 10). N is the number of inputs and outputs of the circuit, and D is the number of stages. The i-th of the following D-1 lines contains N integers wi1, wi2, ..., wiN (1 ≤ wij ≤ N), which describe the wiring between the i-th and (i+1)-th stages. wij means the j-th input of the i-th stage is wired to the wij-th output of the (i+1)-th stage. You can assume wi1, wi2, ..., wiN are distinct for each i.

Output

Print "Yes" on one line if the circuit works as an N sorting network. Print "No" otherwise.

Examples2

Example 1
Input
```
4 4
1 3 4 2 
1 4 2 3 
1 3 2 4
```
Expected output
```
Yes
```
Example 2
Input
```
4 3
3 1 2 4
1 3 2 4
```
Expected output
```
No
```