Problem : 97 - 我的朋友很少

Problem Statistics

Solved Member: 9　　Submission: 84　　User Tried: 11

Statement:

這題要討論的是現充與廚二病的關係。

說到現充，你會想到什麼：
1.很受歡迎，摸貼摸貼
2.人生勝利組
3.爆発しろう
4.死ね！

至於廚二呢...
1.不受歡迎
2.就廚啊
3.因為廚，所以想到邪氣眼
4.實用(變態限定

在研究心理學的你，決定來幫你的 N 個由 1 標號到 N 的朋友們分類成現充以及廚二兩種種類。
其中，每個廚二跟每個廚二之間互相不認識，每個現充與現充之間都互相認識。
你希望，N個人當中至少有 1 個以上的廚二以及 1 個以上的現充。

你想知道，總共有幾種分類方法可以合法分類你的 N 個朋友。

Input:Output:

第 1 行有一個正整數 N(N <= 5000)，代表你有多少個朋友。
接下來有 N 行，第 i+1 行最剛開始有個整數 Ni，後面接著 Ni 個正整數，代表 i 所認識的人們。
測資保證認識的關係必定為雙向，也就是「A認識B」則一定也有「B認識A」。

輸出請輸出一個行整數，代表有多少種分類方法。
如果沒有任何一種方法滿足你的要求，那麼請輸出0。

Sample Input:Sample Output:

4
2 2 3
2 1 3
3 1 2 4
1 3

HINT:

有三種方法：1,4當廚二、4當廚二、2,4兩人都是廚二。

這題測資將近500MB，全部TLE會非常刺激>///<...
所以請盡量優化輸入節省等待時間(總共約差70秒左右吧...囧)。

Source:

POI 18 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-ocen	1000ms	131072kb
1-1	1000ms	131072kb	10
1-2	1000ms	131072kb
1-3	1000ms	131072kb
1-4	1000ms	131072kb
1-5	1000ms	131072kb
2-ocen	1000ms	131072kb
2-1	1000ms	131072kb	10
2-2	1000ms	131072kb
2-3	1000ms	131072kb
3-ocen	1000ms	131072kb
3-1	1000ms	131072kb	10
3-2	1000ms	131072kb
3-3	1000ms	131072kb
4-ocen	1000ms	131072kb
4-1	1000ms	131072kb	10
4-2	1000ms	131072kb
4-3	1000ms	131072kb
5-ocen	5000ms	131072kb
5-1	1000ms	131072kb	10
5-2	1000ms	131072kb
5-3	1000ms	131072kb
6-1	1500ms	131072kb	10
6-2	4500ms	131072kb
6-3	6500ms	131072kb
7-1	2500ms	131072kb	10
7-2	2500ms	131072kb
7-3	12000ms	131072kb
8-1	8500ms	131072kb	10
8-2	13000ms	131072kb
8-3	17000ms	131072kb
9-1	21000ms	131072kb	10
9-2	26000ms	131072kb
9-3	41000ms	131072kb
10-1	46000ms	131072kb	10
10-2	41000ms	131072kb
10-3	61000ms	131072kb
10-4	61000ms	131072kb
10-5	33000ms	131072kb