TopCoder

User's AC Ratio

88.2% (15/17)

Submission's AC Ratio

47.2% (34/72)

Tags

Description

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

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

Input Format

第一行有兩個正整數$N$, $M$,表示共有$N$個人和$M$對朋友。接下來有$M$行,每行有兩個相異非負整數$p_i$ , $q_i$,表示第$p_i$個人和第$q_i$個人是朋友。
$N \le 100000$
$M \le 300000$
$1 \le p_i , q_i \le N$

Output Format

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

Sample Input

//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

//output #1
1

//output #2
0

Hints

Problem Source

Subtasks

For Testdata: 0 ~ 9, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144