DOMINO1 - The Longest Chain of Domino Tiles

no tags 

You are given N domino tiles. Each tile is made of some number of squares (not necessarily two), and each square is coloured either white or black (we use the Croatian letters: B for white and C for black).

Find the longest chain that can be made of these tiles. Each tile can be used at most once and cannot be rotated (for example, BC cannot become CB). The chain is made by a common rule: in adjacent tiles, touching squares must be of the same colour.

Input

[N ≤ 100, the number of dominoes]

in the next N lines:

[a string of size between 1 and 100, representing the domino]

Output

The length of the longest chain.

Example

Input:
4
CB
BCC
BBCC
BCBBC

Output:
11

hide comments
Kashyap Krishnakumar: 2011-09-14 09:33:44

Really nice problem. Loved solving it.

Adrian Satja Kurdija: 2011-09-14 09:33:44

Sorry. I forgot to enable all the test cases: only the first test case was tested. Now the brute force doesn't work.

UPDATE: a rejudge made!

Last edit: 2011-05-04 07:00:48
cegprakash: 2011-09-14 09:33:44

will brute force work?

edit: brute doesn't work now :D

edit: thanks for rejudge!! needs some paper and pencil work :)

Last edit: 2011-05-14 11:26:04

Added by:Adrian Satja Kurdija
Date:2011-05-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem