Maximizing Complementary Stick Connections

You are given n sticks. Each stick has two numbers, one on the left and one on the right, and each number is from the set \(\{0,1,2\}\). You can flip any stick so that the left and right numbers swap, and you must arrange all the sticks in a row. For any two consecutive sticks, let the right number of the left stick be \(x\) and the left number of the right stick be \(y\). The connection between these two sticks is considered valid if \(x+y=3\) (in other words, one number is 1 and the other is 2). Your task is to arrange and orient the sticks so that the number of valid adjacent connections is maximized.

Example: Consider two sticks:

• Stick 1: 1 - 2
• Stick 2: 1 - 0

If they are arranged as 1 - 0, 1 - 2, the connection between the two sticks is between 0 and 1 (0 + 1 = 1), which is not valid. However, if stick 2 is flipped and the sticks are arranged as 1 - 2, 1 - 0, then the connection is between 2 and 1, which gives \(2+1=3\) and is valid. In this case, the maximum number of valid connections is 1.

Note: Even though you must use all the sticks, you are allowed to place some sticks in positions where their connection does not yield a valid sum. Your goal is to maximize the number of internal boundaries (i.e. between sticks) such that the two numbers on either side sum to 3.

Insight: A valid connection requires one endpoint to be 1 and the other to be 2. Sticks that originally have both 1 and 2 (in any order) can be used in the chain and are flexible. Sticks that have only one number in \(\{1,2\}\) (with the other number being 0) or have two identical numbers (either 1 or 2) can only contribute one good endpoint (and hence are best suited as an endpoint in the chain).

The maximum number of valid connections can be computed as follows:

[ \text{Let } A \text{ be the number of sticks with the set }{1,2}. ] [ \text{Let } num_1 \text{ be the count of sticks that can only supply the number } 1. ] [ \text{Let } num_2 \text{ be the count of sticks that can only supply the number } 2. ]

If at least one stick from category A exists, you can arrange all these flexible sticks in a chain yielding \(A-1\) valid connections. Moreover, you can extend the chain by adding an extra stick at one or both ends if you have a partial stick that supplies the required good number. In that case, the maximum number of valid connections is:

[ \text{answer} = A - 1 + \begin{cases} 2, & \text{if } num_1>0 \text{ and } num_2>0,\ 1, & \text{if exactly one of } num_1 \text{ or } num_2 \text{ is positive,}\ 0, & \text{otherwise.} \end{cases} ]

If there are no sticks with both 1 and 2 (i.e. \(A = 0\)), then you can form at most one valid connection provided that you have at least one stick that supplies 1 and another that supplies 2. Otherwise, the answer is 0.

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)), the number of sticks. The following n lines each contain two integers representing the numbers on the left and right of a stick. Each number is either 0, 1, or 2.

outputFormat

Output a single integer, the maximum number of adjacent connections (boundaries) that sum to 3.

sample

2
1 2
1 0

1

</p>