Exclusive Access 2

After studying mutual exclusion protocols in an earlier competition, you now face a harder problem. You run a large enterprise system with many processes running concurrently. The system has several resources - databases, message queues, and so on. Each process works with exactly two resources at a time. For example, one process might copy a job from a particular database into a message queue, while another takes a job from that queue, performs it, and puts the result into a different queue.

Every resource is protected from concurrent access by a mutual-exclusion lock. To use a resource, a process acquires that resource's lock, does its work, then releases the lock. No two processes may hold the same lock at the same time (mutual exclusion), so a process that tries to acquire a lock must wait if the lock is already held by another process.

The main loop of a process that works with resources P and Q looks like this:

loop forever
  DoSomeNonCriticalWork()
  P.lock()
  Q.lock()
  WorkWithResourcesPandQ()
  Q.unlock()
  P.unlock()
end loop

The order in which the two locks are taken matters. Suppose process c has acquired lock P and is waiting for lock Q. Then Q is held by some other process d. If d is working (not waiting), we say there is a wait chain of length 1. If d holds Q and is waiting for another lock R held by a working process e, the wait chain has length 2, and so on. If some process in the chain is waiting for lock P, which is already held by process c, the wait chain is infinite and the system deadlocks.

We are interested only in alternating wait chains, in which every process holds its first lock and waits for its second. Formally:

An alternating wait chain of length n (n >= 0) is an alternating sequence of resources R0, R1, ..., R(n+1) and distinct processes c0, c1, ..., cn, written R0 c0 R1 c1 ... Rn cn R(n+1), where process ci acquires the locks for Ri and R(i+1) in that order. The chain is a deadlock when R0 = R(n+1).

You are given the two resources that each process uses. You may decide, for every process, the order in which it acquires its two locks, so that the system never deadlocks and the largest possible alternating-wait-chain length is as small as possible. Report that smallest achievable maximum length.

The first line contains one integer n (1 <= n <= 100) - the number of processes.

Each of the next n lines describes one process and contains two distinct resources separated by a space. Every resource is an uppercase letter from L to Z, so there are at most 15 distinct resources.

Print one integer m - the smallest possible length of the longest alternating wait chain, minimized over all choices of lock-acquisition order for the processes that keep the system deadlock-free.

Any deadlock-free assignment of lock orders may achieve this minimum; only the resulting value m is required.