TSSTR - Shortest Superstring

no tags 

Input

Input begins with a single integer t (t = 1000). t test cases follow.

Each test case starts with a line containing integer n denoting the number of words (1 <= n <= 100). Each of the next n lines contains a word - a string of between 4 and 16 characters 'a', 'b', 'c' or 'd'.

Output

For the i-th test case output a line with the text case i Y or case i N, specifying whether you wish to solve the given case. Then in the former case print a single line containing the shortest superstring. Exactly n lines with a single integer on each should follow, the i-th representing the position of the first letter of the i-th word.

Scoring

The score awarded to your program is the sum of scores taken over all test cases you chose to solve.

For each test case, the score is the fraction of the total number of characters of the words and the number of characters of the text. Programs which receive a negative score for some test case will be considered incorrect.

Example

Input:
1
4
aaaa
aaaa
aaaa
bbaaa

Output:
case 1 Y
aaaabbaaaa
1
1
7
5

Score:
17/10 = 1.7
Bonus info: If score = xxx.xxxaaa, aaa means the number of test cases with Y answer.

hide comments
likhith: 2017-04-22 10:59:33

shortest super string can be "bbaaaa" so that answer is
3
3
3
1.....please help me

Last edit: 2017-04-22 11:01:07
baton112: 2016-04-03 17:40:12

for some reason
case 1 Y
aaaaaaaaaaaabbaaa
1
1
1
13
is incorrect but
case 1 Y
aaaaaaaaaaaabbaaa
1
5
9
13
is perfecly fine :P

xpshekhar: 2015-12-27 22:10:03

the program is well compiled and accepted.
but,getting 0.
why and what is the meaning of 0 here?
please,tell me some1.

Last edit: 2015-12-27 22:10:38
:D: 2013-01-29 07:21:13

B is a superstring of A if some consecutive characters in B form A.

deepika bagaria: 2013-01-28 17:55:08

please explain what is super string!!!!!!!!
thnx

Last edit: 2013-02-10 20:05:49
(Tjandra Satria Gunawan)(曾毅昆): 2012-07-10 18:41:37

Optimal Solution:
superstring: "bbaaaa"
score: 17/6=2.83333333 point(s)

Aditya Pande: 2012-05-27 11:05:40

the solution in example is not optimal solution
ur solution wud get 17/9=1.77777 pts

unXled: 2012-05-21 10:12:10

can the answer for 3rd aaaa be 1
nd the shortest superstring can be
aaaabbaaa (9 digits) then why 10 digits string is given as shortest....
please someone clear this doubt.....


Added by:mima
Date:2005-05-18
Time limit:12.17s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET