Bobo มีกราฟไม่มีทิศทางที่เชื่อมต่อกัน $G$ ซึ่งมีจุดยอด $n$ จุดและเส้นเชื่อม $m$ เส้น โดยกำกับจุดยอดด้วยหมายเลข $1,2,\ldots,n$ เพื่อความสะดวก

Bobo เลือกสับเซตที่ไม่ว่างของเส้นเชื่อม โดยให้กราฟที่มีเส้นเชื่อมที่เลือกยังคงเชื่อมต่อกัน เขาต้องการทราบจำนวนสับเซตดังกล่าว modulo $2$

โปรดทราบว่ากราฟเชื่อมต่อกันก็ต่อเมื่อ สำหรับจุดยอดสองจุดใด ๆ $a$ และ $b$ มีเส้นทางที่เชื่อม $a$ กับ $b$

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีกรณีทดสอบตั้งแต่ศูนย์กรณีขึ้นไป และสิ้นสุดเมื่อถึงจุดสิ้นสุดไฟล์ สำหรับแต่ละกรณีทดสอบ:

บรรทัดแรกมีจำนวนเต็มสองจำนวน $n$ และ $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$)

บรรทัดที่ $i$ ของ $m$ บรรทัดถัดไปมีจำนวนเต็มสองจำนวน $a_i$ และ $b_i$ ซึ่งแทนเส้นเชื่อมระหว่างจุดยอด $a_i$ กับ $b_i$

รับประกันว่าผลรวมของ $m$ ทั้งหมดไม่เกิน $2 \cdot 10^5$ และกราฟที่ให้มาทุกกราฟเชื่อมต่อกัน

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์จำนวนเต็มที่แทนเศษจากการหารด้วย $2$

ตัวอย่าง

ข้อมูลนำเข้า 1

2 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1

ข้อมูลส่งออก 1

1
1
0