1985 . 提姆提姆
TopCoder
Tags
Description
前情提要。
由於你的協助，提姆們進化成提姆提姆了！
雖然提姆提姆是由提姆進化來的，但是它們實際上有很大的差別。提姆提姆擁有更強的能力，可以切換成許多種不同的戰鬥模式，每種戰鬥模式能解決的敵人類型都不同。但是提姆提姆不喜歡團隊合作，它們喜歡單打獨鬥。
小向有$N$隻提姆提姆，理所當然地，她準備了$N$個不同的任務，由$0$編號到$N-1$，希望$N$隻提姆提姆每隻各解決一個任務，把這$N$個任務全部完成。然而因為提姆提姆們的戰鬥模式實在是太多了，小向不知道要怎麼安排任務會比較好。
於是小向找到了你。現在給你一堆提姆提姆、一堆任務，還有提姆提姆們在不同模式下能夠解決的任務列表，請你幫小向找到一種安排任務的方法，順便算一下小向總共有幾種不同的方法安排任務。
喔對了，由於安排任務的方法數可能是凡人無法理解的魔法數字，你只要計算答案模$10^ 9+9$的餘數就好了。
（一隻提姆提姆用不同戰鬥模式解決同一個任務要算是不同的安排。）
Input Format
第一行有兩個正整數$N, sub$，分別代表提姆提姆的數量與子任務編號。
接下來會以數行代表一隻提姆提姆的資訊：
第一行有一個正整數$p_i$，代表這隻提姆提姆有幾種戰鬥模式（戰鬥模式由0編號到$p_i-1$）；
接下來$p_i$行，每行第一個數字為非負整數$c_{ij}$，代表在第$j$種戰鬥模式中這隻提姆提姆能夠解決幾個任務；接下來有$c_{ij}$個以空白隔開的數字，代表這隻提姆提姆在這種戰鬥模式中能解決的任務編號。
這個格式會重複$N$次，直到所有提姆提姆都被描述完畢為止。
以下以$C$代表提姆提姆的戰鬥模式數量上限。
對於所有測資，$N\leq 24, C\leq 1000$。保證一定有方法可以安排任務。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~3) | $N,C\leq 10$ | 17 |
| 2 (0~7) | $N,C\leq 15$ | 13 |
| 3 (0~11) | $N\leq 20$ | 20 |
| 4 (12~15) | 無限制；方法數量錯誤不影響得分 | 18 |
| 5 (0~19) | 無限制 | 32 |
Output Format
第一行輸出一個數字，代表安排任務的方法數模$10^ 9+9$的餘數。
接下來$N$行，請輸出一種可行的安排方法。每行輸出兩個非負整數$p_i, q_i$，代表這隻提姆提姆應該用第$p_i$種戰鬥模式完成第$q_i$個任務。輸出的提姆提姆順序需與輸入順序相同。
Sample Input 1
1
1 0
2
2 1 0
1 1
Sample Output 1
0 0
0 1
Hints
範例測資中，由於第一隻提姆提姆必須做編號0的任務，因此第二隻只能做編號1的任務；而第二隻可以用兩種不同的戰鬥模式做編號1的任務。
Problem Source
Problem Set / Description by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 17 |
| 2 | 0~7 | 13 |
| 3 | 0~11 | 20 |
| 4 | 12~15 | 18 |
| 5 | 0~19 | 32 |