Во една земја се водат преговори помеѓу најголемите две партии за организирање на нови избори. Овие партии, иако навидум не се во добри меѓусебни односи, сепак се согласуваат дека не треба да дозволат појавување на нова јака партија во државата, која ќе може да ја загрози нивната положба. Нивното стравување е од експанзија на некоја локална партија.

Локална партија може да претставува опасност ако биде поддржана од граѓаните од три меѓусебно блиско поврзани градови (сите три градови се директно меѓусебно поврзани со пат). Со други зборови, ако постојат три градови A, B, C и постои директен пат (пат кој не поминува низ други градови) меѓу А и B, директен пат меѓу B и C, и директен пат меѓу A и C, тогаш тоа е опасна ситуација која двете најголеми партии не сакаат да ја дозволат. (Сите патишта во државата се двонасочни.)

Двете партии може да одлучат за форматот на изборите и тие планираат организирање на избори само во некои градови во државата. Значи, за да избегнат опасни ситуации тие едноставно можат да решат во еден (или повеќе) од градовите да нема избори.

Доколку ви се дадени информации за градовите во државата и како тие се меѓусебно поврзани со патишта, напишете програма која ќе пресмета колку различни начини постојат за одбирање на градовите во кои ќе се организираат избори, а притоа да нема ниту една опасна ситуација за двете најголеми партии. Два начини се различни доколку постои град X каде се организираат избори во едниот начин, но во тој град не се организираат избори во другиот начин.

Да го објасниме проблемот и поинаку. Ако имаме N градови (1, 2, 3, …, N), може да се разгледуваат подмножествата од овие градови во кои може да се организираат избори (на пример {1, 3}, {1, 2, 3, 5}, итн). Ваша задача е да го пресметате и отпечатите бројот на различни подмножества, каде градовите во подмножеството се прифатливи како листа каде ќе се организираат избори за двете најголеми партии – т.е. да не постои тројка од градови која креира опасна ситуација.

Влез

Во првата линија се запишани 2 цели броеви N (1 <= N <= 30), и M (0 <= M <= 50), кои го означуваат бројот на градови, и бројот на патишта, соодветно.

Во секој од следните M редови се запишани по два цели броја Ai и Bi (1 <= Ai, Bi <= N), кои означуваат дека постои двонасочен пат помеѓу градовите Ai и Bi. Нема да постојат два патишта кои поврзуваат ист пар на градови, и Ai секогаш ќе биде различно од Bi (нема да постои пат од еден град, до истиот тој град).

Забелешка: Во тест случаи кои носат најмалку 30% од поените, N ќе биде цел број помал или еднаков на 10.
Во други тест случаи кои носат најмалку 30% од поените, N ќе биде цел број поголем од 10, и помал или еднаков на 22.

Излез

Отпечатете го бараниот број на подмножества.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3 3
1 2
3 1
2 3

излез
7

влез
4 4
1 2
3 1
4 3
2 3

излез
14

влез
4 4
1 2
2 3
3 4
1 4

излез
16

Објаснување за првиот пример: Валидни подмножества се {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}. Не може да се распишат избори во градовите {1, 2, 3}, бидејќи тогаш постои тројка од градови {1, 2, 3}, каде постои пат од 1 до 3, пат од 2 до 3, и пат од 3 до 1.

Забележете дека го избројавме и празното подмножество {}. Едноставно, партиите можат да одлучат да нема избори во ниту еден град, и самите да се договорат кој ќе биде на власт и во кој период.