정렬 네트워크 검사

N 정렬 네트워크는 N개의 수를 입력받아 정렬된 순서로 출력하는 회로다. Smith 씨는 여러 크기의 회로를 파는 회사의 엔지니어다.

어느 날 회사는 N 정렬 네트워크 주문을 받았다. 그런데 그때는 N개의 수를 처리하는 회로가 없었다. 직원은 재고가 없다며 주문을 거절했지만, 고객이 너무 급한 나머지 일주일 안에 회로를 받으면 큰돈을 주겠다고 했다. 이 건은 관리자에게 올라갔고, 관리자는 Smith 씨에게 마감까지 N 정렬 네트워크를 만들어 낼 방법을 물었다.

그는 N/2 정렬 네트워크 재고가 많다는 것을 알고, 그것들을 여러 개 조합할 방법을 떠올렸다. N/2 정렬 네트워크로 새 회로를 설계했지만, 그것이 정말 N 정렬 네트워크로 동작할지는 확신할 수 없었다. 그래서 동료인 당신에게 실제로 N 정렬 네트워크인지 확인해 달라고 부탁했다.

그가 설계한 회로는 여러 단으로 이루어진다. 각 단은 N/2 정렬 네트워크 두 개로 구성되므로, 각 단은 N개의 수로 이루어진 수열을 입력받아 N개의 수로 이루어진 수열을 출력한다. 한 단의 1번째부터 N/2번째 입력은 두 N/2 정렬 네트워크 중 하나로 들어가고, (N/2+1)번째부터 N번째 입력은 다른 하나로 들어간다. 마찬가지로 한 단의 출력 중 앞 절반은 앞쪽 정렬 네트워크의 출력이고 뒤 절반은 뒤쪽 정렬 네트워크의 출력이며, 둘 다 오름차순으로 정렬되어 있다. 각 단의 출력은 다음 단의 입력과 정확히 하나씩 연결되고, 서로 다른 두 입력이 같은 출력 선에 연결되지 않는다. 마지막 단의 입력이 회로 전체의 입력이고, 첫 번째 단의 출력이 회로 전체의 출력이다.

첫 줄에 양의 짝수 N (4 ≤ N ≤ 100)과 양의 정수 D (1 ≤ D ≤ 10)가 주어진다. N은 회로의 입력과 출력의 개수이고, D는 회로의 단 수이다. 이어지는 D-1개 줄 중 i번째 줄에는 N개의 정수 wi1, wi2, ..., wiN (1 ≤ wij ≤ N)이 주어지며, 이는 i번째 단과 (i+1)번째 단 사이의 배선을 나타낸다. wij는 i번째 단의 j번째 입력과 (i+1)번째 단의 wij번째 출력이 연결되어 있음을 뜻한다. 각 i에 대해 wi1, wi2, ..., wiN은 서로 다르다고 가정할 수 있다.

회로가 N 정렬 네트워크로 동작하면 "Yes"를, 그렇지 않으면 "No"를 한 줄에 출력한다.