1122 : ตั้งวงดนตรี (band)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

คุณได้รับเชิญมาเป็นอาจารย์สอนวิชาคอมพิวเตอร์ในค่ายอบรมเข้มแห่งหนึ่ง ซึ่งมีนักเรียนอยู่ทั้งหมด N คน คุณได้พบว่า นักเรียนในค่าย นอกจากจะมีความสามารถในการเขียนโปรแกรมคอมพิวเตอร์แล้ว ยังมีความสามารถในการเล่นดนตรีอีกด้วย คุณจึงมีความคิดที่จะจัดตั้งวงดนตรี light music ประจำค่ายขึ้นมา

วงดนตรี light music นั้น ประกอบด้วยสมาชิก 4 คน ซึ่งแต่ละคนก็จะมีหน้าที่ในการเล่นกีตาร์ เบส กลอง และคีย์บอร์ด คุณต้องการเลือกนักเรียนในค่าย 4 คน มาเข้าร่วมเป็นสมาชิกวงดนตรี สำหรับนำไปแสดงในการแข่งขันดนตรีนานาชาติ International Olympiad in Instrument (IOI) ครั้งที่ 22 ที่ประเทศแคนาดา เพื่อสร้างชื่อเสียงให้กับประเทศชาติและค่ายอบรมเข้มแห่งนี้

อย่างไรก็ตาม ด้วยความที่ในค่ายมีนักเรียนอยู่เป็นจำนวนมาก ทำให้นักเรียนในค่ายไม่สามารถรู้จักกันได้อย่างทั่วถึง นักเรียนบางคนก็เป็นเพื่อนกัน ในขณะที่บางคนก็ไม่รู้จักกันเลย ความเป็นเพื่อนจะมีลักษณะสมมาตรเสมอ (นั่นคือถ้า A เป็นเพื่อนกับ B แล้ว B ก็จะเป็นเพื่อนกับ A ด้วย) และการที่จะตั้งวงดนตรีให้ได้อย่างมีประสิทธิภาพนั้น สมาชิกในวงจะต้องมีความสนิทสนมกลมเกลียวกันเป็นอย่างดี กล่าวคือ เมื่อเราพิจารณาคู่ของสมาชิก 2 คนใดๆ ในวง ซึ่งมีอยู่ทั้งหมด 6 คู่ จะต้องมีอย่างน้อย 5 คู่ ที่เป็นเพื่อนกัน นั่นคือมีสมาชิกที่ไม่เป็นเพื่อนกันได้อย่างมากเพียงคู่เดียว

คุณต้องการทราบว่า มีวิธีในการเลือกนักเรียนในค่าย 4 คน มาเป็นสมาชิกวงดนตรีอยู่ทั้งหมดกี่วิธี

งานของคุณ
จงเขียนโปรแกรมเพื่อรับจำนวนนักเรียนในค่าย และความเป็นเพื่อนของนักเรียนแต่ละคู่ แล้วคำนวณว่า มีวิธีในการเลือกสมาชิกวงดนตรีอยู่ทั้งหมดกี่วิธี

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ M (4 ≤ N ≤ 1,000; 1 ≤ M ≤ 5,000) แทนจำนวนนักเรียนในค่าย และจำนวนคู่ของนักเรียนที่เป็นเพื่อนกัน นักเรียนแต่ละคนจะมีหมายเลขประจำตัวตั้งแต่ 1, 2, 3 เรียงไปเรื่อยๆ จนถึง N

อีก M บรรทัดต่อมา ในแต่ละบรรทัดจะระบุจำนวนเต็ม X และ Y ที่แตกต่างกัน 
(1 ≤ X,Y ≤ N) ซึ่งหมายความว่า นักเรียนหมายเลข X เป็นเพื่อนกับนักเรียนหมายเลข Y

ข้อมูลส่งออก
มีบรรทัดเดียว แสดงจำนวนวิธีทั้งหมดในการเลือกสมาชิกวงดนตรี

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 100

ที่มา
การแข่งขัน IOI Thailand League เดือนมิถุนายน 2553
โจทย์โดย: สุธี เรืองวิเศษ


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
4 5
1 2
1 3
1 4
2 3
2 4
1
6 12
1 2
2 3
3 1
4 1
4 2
4 3
5 1
5 2
5 3
6 1
6 2
6 3
12

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 17 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)