TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

86.1% (31/36)

Submission's AC Ratio

35.8% (77/215)

Tags

Description

你有個可愛的妹妹,和她生活一起17年了,今天是她的生日,你為她準備了她最愛的橘子口味冰淇淋,
她臉頰微紅,有點忸捏的對你說:「謝謝歐尼醬>/////<,我有點話想對你說..........其實我只是你的幻想」
你呆望著一個冰淇淋甜筒插在空氣填充物上,突然站起奪門而出,開始了你的幻想宅之旅

跑了一會,你漸漸放慢腳步,手撐著膝大口喘氣,你環顧了四周,發現周遭的人都是有一隻手粗,一隻手細,其中有些人頭戴尖頂帽,彌漫著神祕感,你心想「那一定是魔法師了吧!」,此時旁邊一個帶著墨鏡的人忽然靠過來對你說:「不,那些人只是和你有些像的中二幻想宅」,當你正詫異感到疑惑時,墨鏡又說:「我是墨鏡之王,能看透人心,真正的魔法溼可是大(其)智(貌)若(不)愚(揚)的呢!」,你欲開口,又被打斷:「想成為魔法師嗎?那你必須通過魔法溼協會(Magic of Gathering,MOG)的檢定呢」說完,那個人消逝在風中.
你走到櫃台,櫃台人員卻說報考年齡至少要三十歲,你沮喪的走到大道上,被一個邋褟的人撞倒在地上,你欲對他揮拳,但想想同為可憐人,打消了念頭,邋褟人對你說:「你能幫我解個問題嗎?(也不等答覆就自顧自的講下去),我給你一群人的關係,你把他們分成兩個團體,使團體內的的人互不是好朋友.」身為專業的幻想宅,你知道這一定是某個flag,幫助邋褟人解出問題吧!

Input Format

第一行有兩個正整數N, M,表示共有N個人和M對朋友。接下來有M行,每行有兩個相異非負整數pi , qi,表示第pi個人和第qi個人是朋友。
N100000
M300000
1pi,qiN

Output Format

設總共有K種分法,輸出K mod 1000007之值

Sample Input 1

//input #1
5 4
1 2
5 2
2 3
3 4

//input #2
5 7
1 2
1 3
1 5
4 3
4 5
2 3
3 5

Sample Output 1

//output #1
1

//output #2
0

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1