2M scientists are supposed to present papers in a conference in a day. The day is divided into 2
slots, the morning slot and the evening slot. M scientists present their paper in the morning slot
and the remaining in the evening slot. Both slots are separated by a lunch break.
Some scientists depend on a paper from some other scientists to be presented before theirs. So if
Scientist A is presenting a paper on "Graph Theory" and Scientist B on "Max flow-Min cut",
then A has to present before B. Lunch break is a time of merry making and partying, so attendees
tend to forget the papers in the previous half. Due to this, the dependent scientist (B in this case)
has to present the paper in the same slot as the scientist on whom he is dependent (A in this
case). Given the dependencies, find the number of possible orderings of presenting the papers.
The first line of input will contain an integer T <= 100 denoting the number of test cases.
Each test case will be formatted as follows:-
The first line will contain an integer denoting 1<= M <= 8.
The next 2M lines will contain 2M characters each. Each character will either be 'Y' or 'N'. If the i th line's j th character is 'Y' it means that scientist i is dependent on scientist j. 'N' signifies no dependence. A scientist will never be dependent on himself.
Output one line per case that contains an integer denoting the number of possible ordering of
scientists.
3 2 NNNN NNNN NNNN NNNN 2 NYNN NNNN NNNY NNNN 2 NYYY YNYY YYNY YYYN
24 2 0
Migrated from old NTUJ.
ICPC 2008, Amritapuri
| No. | Testdata Range | Score |
|---|