Longest Article

All submissions for this problem are available.
In Chefland every word contains exactly two letters. There exist two alphabets A of size N and B of size M, where the first letter of every word comes from A, and the second letter of every word comes from B.
Every sentence is a spaceseparated list of words such that each letter from A is used exactly once in some word of the sentence and each letter from B is used at most once. In particular, each sentence contains exactly N words.
An article contains exactly one sentence per line. Chef would like to avoid excessive word repetition, so he provides an upper bound for each word, specifying the number of times you can use that word in the article. Chef has no time so he asks you to write the longest possible article under the given constraints.
Input
The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test contains an integer N and a string A of length N, denoting the first alphabet. N and A are separated by exactly one space. The next line contains an integer M and a string B of length M, denoting the second alphabet. M and B are separated by exactly one space. Then N * M lines follow. Each of these lines contains twocharacter string W and an integer C(W), denoting the word and the upper bound on the number of times this word can be used in the article. They are separated by exactly one space.
Output
For each test case, output on a separate line an integer K denoting the number of sentences in the longest possible article, followed by the longest article in compressed format on consecutive lines. The first line of the compressed article should contain an integer L, denoting the number of blocks in the article. Each of following L lines should contain an integer R and a sentence S separated by a space. It means that in the actual article, R sentences equal to S follows. If every longest possible article requires more than 30000 blocks in its compressed form, output 1 instead of the compressed article. If there are several longest articles possible you can output any of them.
Constraints
 1 ≤ T ≤ 2
 1 ≤ N, M ≤ 94
 0 ≤ C(W) ≤ 10000000 (10^{7})
 All characters in A are different and A contains exactly N characters
 All characters in B are different and B contains exactly M characters
 Each character in A and B has ASCII code from 33 to 126, inclusive.
 The first character of W is from A and the second one is from B
 All N * M words in the input for the particular test case are different
Example
Input: 2 2 Hi 3 esn is 1 Hs 1 Hn 2 ie 2 in 1 He 2 1 + 1 + ++ 0 Output: 4 3 1 He is 1 in He 2 Hn ie 0 0
Explanation
Example case 1. The complete article is
He is
in He
Hn ie
Hn ie
Note that we use each word maximum number of times except Hs which was not used at all.
Example case 2. We have only 1 word ++ for the given alphabets A and B but Chef does not allow to use it. So the only possible article here is an empty article.
Author:  iscsi 
Tester:  anton_lunyov 
Tags  bipartite, graph, hard, iscsi , march13, maximumflow 
Date Added:  30112012 
Time Limit:  2.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 