Дараагийн Кодфорсесийн раундад зориулан бэлдсэн $n$ бодлого байна. Тэд шийдэхэд хүндрэлтэй байдлаараа өсөхөөр эрэмбэлэгдсэн ба ямар ч хоёр бодлогыг шийдэх хүндрэл нь ижил байхгүй. Мөн түүнчлэн төсөөтэй бодлогуудын $m$ хос байна. Зохиогчид бодлогуудыг дараах дүрмүүдийн дагуу хоёр хэсэгт хуваахыг хүсч байна:

• Хэсэг бүрийн бодлогын бүрдэл хоосон биш байх ёстой.
• Бодлого бүр яг нэг хэсэгт ашиглагдана (тиймээ, энэ жирийн биш шаардлага).
• 1-р хэсэгт ашиглагдсан бодлого бүр 2-р хэсэгт ашиглагдсан бодлого бүрээс хэцүү байх ёстой.
• Хэрвээ хоёр бодлого төсөөтэй бол тэд ялгаатай хэсэгт ашиглагдах ёстой.

Таны зорилго бол бүх нөхцөлийг хангахаар бодлогуудыг хоёр хэсэгт хуваах боломжуудыг тоолох юм. Хэрвээ 1-р хэсэг болон 2-р хэсэгт хамааралтай ядаж нэг бодлогоороо ялгаатай бол уг хоёр хуваалт нь ялгаатайд тооцогдоно.

Төсөөтэй гэх хамаарал нь дамжихгүй. Өөрөөр хэлбэл хэрвээ $i$ бодлого нь $j$ бодлоготой төсөөтэй ба $j$ бодлого $k$ бодлоготой төсөөтэй бол $i$ бодлого $k$ бодлоготой төсөөтэй гэсэн үг биш.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 100 000$, $0 ≤ m ≤ 100 000$) байх ба харгалзан раундад зориулан бэлдсэн бодлогуудын тоо болон төсөөтэй бодлогуудын хосын тоо байна.

Дараагийн $m$ мөр бүрт төсөөтэй бодлогын хос $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}$) байна. Ямар ч хос бодлого оролтонд хоёр байхгүй нь тодорхой.

Гаралт

Бодлогуудыг хоёр хэсэгт хуваах боломжит замуудын тоог илэрхийлэх бүхэл тоон утгыг хэвлэ.

Эхний жишээн дээр $1$ ба $2$ бодлогууд нь 2-р хэсэгт ашиглагдах ёстой бол $4$ ба $5$ бодлогууд 1-р хэсэгт ашиглагдах ёстой. $3$-р бодлого 1 эсвэл 2-р хэсэгт алинд нь ч ашиглагдаж болно.

Хоёр дахь жишээн дээр бодлогуудын бүх хос төсөөтэй ба ямар ч дүрмийг зөрчихгүйгээр бодлогуудыг хоёр хэсэгт хуваах боломж байхгүй.

Гурав дахь жишээ танд төсөөтэй хамаарал дамжихгүй гэдгийг сануулна. $3$-р бодлого $1$ ба $2$ аль алинтай нь төстэй боловч $1$-р бодлого $2$-той төстэй биш, иймд тэд цуг ашиглагдаж болно.