파댕이의 예술작품

파댕이는 근무하던 중 자신의 예술성을 깨달았고, 사직서를 낸 후 예술가가 되었다!

파댕이는 유명한 예술가가 되고 싶어 여러 작품을 만든다. 이번에는 4차원 구조물을 만들 예정이다.

파댕이가 만들 작품은 정십육포체의 바깥을 둘러싸는 16개의 정사면체의 중심에 빛이 나는 전구를 장착해 빛나는 정십육포체이다. 파댕이가 사용할 전구는 한 개 또는 두 개의 정사면체를 동시에 빛나게 할 수 있다. 두 개의 정사면체를 동시에 빛나게 하기 위해서 두 정사면체가 만나는 교면의 중심에 구멍을 뚫었다. 이 구멍을 통해서 두 개의 정사면체가 동시에 빛나게 할 전구를 통과시킬 수 있다. 파댕이는 돈이 모자라 전구에 드는 돈을 최대한 아끼고자 한다.

하지만 파댕이가 만든 정십육포체의 몇 개의 면에는 전구가 통과할 구멍이 없다! 파댕이를 도와 정십육포체의 정사면체를 모두 빛나게 하는 데 필요한 전구의 최소 개수를 구해주자.

정십육포체를 둘러싸는 정사면체에 $1$번 정사면체는 $2$, $3$, $4$, $5$번 정사면체와 이웃하고, $2$번 정사면체는 $6$, $7$, $8$번 정사면체와 이웃하고, $3$번 정사면체와 $6$, $9$, $10$번, $4$번 정사면체와 $7$, $9$번 정사면체가 이웃하도록 번호를 붙였다. 서로 반대편 정사면체와의 번호 합은 항상 $17$이다.

첫 번째 줄에 파댕이가 전구가 통과할 구멍을 뚫지 못한 면의 개수 $N$이 주어진다. $(0≤ N ≤ 32)$

두 번째 줄부터 $N$개의 줄에 걸쳐 파댕이가 뚫지 못한 면을 사이에 둔 두 정사면체의 번호 $a,b$가 공백으로 구분되어 한 줄에 하나씩 주어진다. $(1≤ a < b ≤ 16)$

주어지는 모든 면은 중복되어 주어지지 않는다.

파댕이가 사용해야 할 전구의 최소 개수를 출력한다.