Hide

Problem C
Swish

/problems/swish/file/statement/en/img-0001.jpg
Swish (TM) is published by ThinkFun.com

You and your friends are playing a card game called “Swish.” In Swish, each player tries to collect as many cards as possible from the table by collecting them in groups called “swishes.” Almost all the cards from the table have been collected so far, and so you wonder if there is a way to group the remaining cards into swishes so that there are no cards left over.

Each card has exactly $1$ dot and $1$ ring on it. The cards are transparent and rectangular, so you can place them on top of each other and see the rings and dots on the cards underneath. A ring can enclose a dot if they share the same position. Each dot/ring pair can be in one of exactly $12$ positions on the card, which are numbered as shown in the Figure below:

\includegraphics[width=0.17\textwidth ]{cardpositions}
Figure 1: Possible positions for rings and dots on each card.

A swish is formed by choosing an arbitrary card to be the start of a pile, then adding more cards to the pile so that a new card has a ring which encloses the previous card’s dot, and so that the dot of the added card does not overlap any ring/circle pairs already placed. Cards can be flipped and/or rotated in any way when they are being added to a swish, but the cards must lay exactly on top of each other and must maintain a “portrait” orientation (being taller than it is wide). The last card chosen must have a dot which is enclosed by the first card’s ring. By forming swishes in this way, a valid swish cannot contain a smaller swish if all the card orientations are kept the same. A valid “swish” can contain anywhere from $2$ to $12$ cards.

Is it possible to group all the cards from the table into swishes, and if so, what is the minimum number of swishes necessary to do so?

Input

The input consists of a single test case. The first line of input contains a single integer $n$, where $1 \leq n \leq 20$ is the number of cards on the table. The next $n$ lines will describe each card. Each line will contain two integers $r$ and $d$, where $0 \leq r, d \leq 11, r \ne d$ are the positions of the ring and dot on that card, respectively.

The positions of the rings and the dots are given in row order, as shown in Figure 1. The positions are symmetric, so that a ring or a dot that is on position $0$ may be rotated and/or flipped so that the position changes to $2, 9,$ or $11$. Similarly, a ring or dot on position $4$ may be flipped and/or rotated so that the position changes to $7$. The other positions may also be changed by rotating and/or flipping the card.

Output

If it is not possible to arrange the cards in swishes so that each card is a part of exactly one swish, then output -1. Otherwise, output an integer denoting the minimum number of swishes so that each card is a part of exactly $1$ swish.

Sample Input 1 Sample Output 1
4
9 4
9 1
4 9
1 9
1
Sample Input 2 Sample Output 2
5
3 6
7 2
11 0
9 4
0 6
-1
Sample Input 3 Sample Output 3
12
6 5
4 0
7 11
5 8
1 6
10 4
11 9
8 9
2 8
3 4
0 1
2 10
1

Please log in to submit a solution to this problem

Log in