규중이가 드디어 취업에 성공했다! 설레는 마음으로 첫 출근을 한 규중이는 앞으로 회사 옥외 광고판 비디오월을 관리하는 일을 하게 된다고 들었다.

규중이네 회사 옥외 광고판 비디오월은 개의 디스플레이 유닛과 1대의 비디오월 컨트롤러로 이루어져 있다. 비디오월 컨트롤러는 원본 입력 화면을 개로 쪼갠 뒤 각각의 디스플레이 유닛으로 송출한다.

규중이는 어제 비디오월 컨트롤러와 개의 디스플레이 유닛을 올바른 위치에 연결하는 케이블 작업을 완벽하게 마치고 즐거운 마음으로 퇴근했다. 이 때 비디오월은 맨 위 행부터 아래 행으로, 각 행에서는 왼쪽에서 오른쪽 순서대로 부터 까지의 화면 조각이 차례대로 송출되고 있었다.

즉, 비디오월의 에는 번 화면이 위치했다.

그러나 규중이가 간과한 사실이 하나 있었다. 바로 규중이의 오랜 라이벌인 선창이가 이미 그 회사에 다니고 있다는 것이었다. 선창이는 규중이를 골탕 먹이기 위해 밤 사이 비디오월 컨트롤러와 디스플레이 유닛을 연결하는 케이블을 무작위로 섞어 놓았고, 심지어 케이블을 물리적으로 고정해 다시 뽑을 수 없게 만들어 버렸다.

다음 날 출근한 규중이는 뒤섞인 화면을 보고 크게 당황했지만, 다행히 수습할 방법은 있었다. 비디오월 컨트롤러가 SWAP 프로토콜을 지원하기 때문이다. SWAP 프로토콜은 두 개의 디스플레이 유닛 위치를 입력받아, 현재 두 유닛에 송출되고 있는 화면을 서로 교환해 주는 기능이다.

이 사태를 최대한 빨리 해결하고 싶은 규중이는 최소 횟수의 SWAP 프로토콜을 사용하여 화면을 원래 상태로 되돌리려고 한다. 규중이를 도와, 엉망이 된 비디오월을 복구하기 위해 입력해야 하는 SWAP 프로토콜 개수를 구하는 프로그램을 작성해 보자.

#539. 라이벌이 너무해

Input

Output

Sample

Input 1

Output 1

Sample

Input 2

Output 2

Time Limit

Memory Limit

Source

Hint

#539. 라이벌이 너무해

Input

Output

Sample

Input 1

Output 1

Sample

Input 2

Output 2

Time Limit

Memory Limit

Source

Hint