비보파크 동물 배치

비보파크는 발렌시아에 있는 동물원이다. 최근에 넓고 평평한 사바나 초원을 여러 우리로 나눈 구역이 새로 생겼다.

새로 만든 우리마다 사자, 표범, 호랑이, 흑표범 네 종 가운데 한 종을 한 마리씩 배치해야 한다. 이 동물은 영역 의식이 강해서, 어느 동물도 자기 우리에서 같은 종의 다른 동물을 볼 수 없어야 한다. 동물원 관리자가 우리 사이의 가시성 자료를 보내 주었으니, 이 자료를 지키면서 모든 우리에 종을 하나씩 정하면 된다. 배치가 끝났을 때 종이 정해지지 않은 우리가 남아 있어서는 안 된다.

첫째 줄에 우리의 개수 $N$이 주어진다. ($1 \le N \le 100$)

둘째 줄부터 파일이 끝날 때까지 가시성 제한이 한 줄에 하나씩 주어진다. 1-3은 1번 우리의 동물이 3번 우리의 동물을 볼 수 있고, 3번 우리의 동물도 1번 우리의 동물을 볼 수 있다는 뜻이다. 관리자가 자료를 꼼꼼히 정리하는 사람이 아니라서 같은 제한이 여러 번 나오거나 두 번호의 순서가 바뀐 채로 다시 나오기도 한다.

모든 제한을 만족하는 배치가 적어도 하나 존재한다.

우리 하나마다 한 줄씩, 우리 번호와 그 우리에 배치한 종의 번호를 공백으로 구분해 출력한다. 종 번호는 1이 사자, 2가 표범, 3이 호랑이, 4가 흑표범이다. 우리 번호는 1번부터 $N$번까지 증가하는 순서로 쓴다.

조건을 만족하는 배치는 여러 가지일 수 있다. 답이 하나로 정해지도록, 1번 우리부터 $N$번 우리까지의 종 번호를 차례로 늘어놓은 수열 $(c_1, c_2, \dots, c_N)$이 사전순으로 가장 작은 배치를 출력한다. 즉 $c_1$을 될 수 있는 대로 작게 정하고, 그 값을 고정한 다음 $c_2$를 될 수 있는 대로 작게 정하는 식으로 마지막 우리까지 정한다.