방어선 무력화

전술 게임에서 치열한 전투를 치르고 있다. 상대 사령관은 본부를 보호하기 위해 원형 진형을 사용하고, 너는 그 방어선을 무력화해서 전투를 이겨야 한다. 적의 원형 진형은 1부터 n까지 번호가 붙은 n명의 병사로 이루어져 있다. 처음에 병사 i와 병사 j는 |i − j| ∈ {1, n − 1}일 때 인접하다.

너에게는 소수의 전사만 있다. 전력이 약해서 병사 둘보다 많거나 인접하지 않은 두 병사와 싸울 수 없다. 게다가 병사 하나를 공격하려 하면 양옆의 병사가 구하러 온다. 그러면 병사 셋과 싸우는 것과 같다. 따라서 인접한 두 병사 사이의 틈을 노려서만 공격할 수 있다. 그렇게 하면 이 두 병사를 쓰러뜨릴 기회가 생긴다. 공격한 뒤 적은 그 틈을 메운다. 예를 들어 병사 1과 2를 쓰러뜨리면 병사 3과 n이 인접하게 된다. 본부를 지킬 병사가 하나도 남지 않을 때까지 병사를 계속 쓰러뜨릴 수 있다.

안타깝게도 어떤 상황에서는 여전히 적을 이길 수 없다. 병사마다 고유한 값이 있고, 서로 다른 값의 종류는 모두 k개 이하다. “뭉치면 살고 흩어지면 죽는다”라는 말을 들어 봤을 것이다. 값이 같은 병사는 뭉칠 수 있고, 값이 다른 병사는 뭉칠 수 없다. 값이 다른 두 병사를 공격하면 항상 쓰러뜨린다. 하지만 값이 같은 두 병사를 공격하면 쓰러지지 않는다.

적의 방어선을 무력화해서 전투를 이기는 공격 전략을 찾는 프로그램을 작성하라. 즉, 원형 진형의 n명 병사를 모두 쓰러뜨려야 한다.

첫째 줄에 두 정수 n과 k가 주어진다. n은 적 병사의 수다. k는 서로 다른 값의 종류 수다. 값은 1부터 k까지 번호가 붙어 있다. 둘째 줄에 n개의 정수 v1, . . . , vn이 주어지며, i ∈ {1, . . . , n}에 대해 병사 i의 값은 vi다.

적의 방어선을 무력화할 방법이 없으면 −1을 출력한다. 그렇지 않으면 n/2개의 줄을 출력한다. i번째 줄에는 i번째 공격을 나타내는 두 정수 pi와 qi를 빈칸 하나를 사이에 두고 출력한다. i번째 공격은 병사 pi와 qi를 쓰러뜨리는 것이다. 이때 두 병사는 인접해야 하고 값이 달라야 한다.

• 2 ≤ k ≤ n ≤ 1000
• n은 짝수다.
• 답이 여러 개라면 그중 아무거나 출력해도 된다.