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
$$: 2013-02-06 21:36:12

weak test case...my code giving 4 for the case: 3 BB CC CB was accepted

Neeraj Pradhan: 2012-04-04 05:38:07

ID :- 6781525 giving wrong answer. Can someone plz give some more test cases as it is giving correct answer even for the test case in the forum.

Nitin Sharma: 2011-10-31 18:47:19

very nice problem !!

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

@nika: it is very useful to learn how to test your solutions. Namely, you make a brute-force solution and a (random) test-case generator, generate about 100 test cases (small enough for brute-force), find the one on which brute-force and your real solution give different answers and then debug. :)

Last edit: 2011-05-12 19:13:23
სვანიძე: 2011-09-14 09:33:44

my code works on my computer but gets WA on spoj. i don't know why prog ID 5072925

Jaros³aw Meller: 2011-09-14 09:33:44

Thank you very much :-) AC now but I must avoid such silly mistakes in the future...

Jaros³aw Meller: 2011-09-14 09:33:44

Can someone give some tricky test cases? Trying to solve it, works fine for all mine test cases, but keep getting WA...

Rachmawan Atmaji Perdana: 2011-09-14 09:33:44

Nice problem, seems like easy but ACC rate is not high. Maybe contains tricky test case

Last edit: 2011-05-05 16:51:14
S: 2011-09-14 09:33:44

another way of asking sort the following :)

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

Really nice problem. Loved solving it.


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