From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details
This question is the third question(Carried 45 marks out of 100) for the Round 2 of 2013 hacker cup. only top 100 contestants will be moved to Round 3.
In this problem you need to count number of possible permutations p of the first N integers, given N-1 constraints of the form pi < pj.
The first line contains an integer T, T ≤ 20, followed by T test cases. Each test case begins with an integer N, N ≤ 1000, which is the number of integers in the permutation. The next N – 1 lines each contain a single constraint in the following format: “i sign j“, where 0 ≤ i, j ≤ N – 1 and sign is either “<” or “>“, which denotes whether the i-th element of the permutation should be less than or greater than the j-th element.
It is guaranteed that it is not possible to partition indices into two disjoint sets A and B such that there is no constraint involving elements from both A and B.