The Enemy of My Enemy

Yongjae has made so many enemies over the years that he spends every day on edge. To prepare for an enemy who could show up at any moment, he decided to make friends. Becoming friends with someone he has no relationship with is hard, so he decided to use the theory that the enemy of my enemy is my friend.

The theory goes like this. If B is hostile to A and C is hostile to B, then A and C are friendly. The theory has a fatal drawback. If D is hostile to C, then A becomes hostile to D as well. And if E is hostile to D, then E turns out friendly with both A and C, and by the same reasoning B and D are friendly too.

Making friends this way also grows the list of enemies, but Yongjae needs friends badly. Nobody in the universe has ever proved the theory rigorously, so before he applies it he wants to check whether it can hold without contradiction among the $N$ people around him. The theory holds if the $N$ people can be split into two camps so that every given hostile pair is split across the two camps, and it fails if some hostile pair ends up inside one camp no matter how the split is made. Help Yongjae find out whether the theory can hold.

The first line contains the number of people around Yongjae, $N$ ($1 \le N \le 2{,}000$), and the number of hostile relations, $M$ ($0 \le M \le 1{,}000{,}000$), separated by a space. Each of the next $M$ lines contains the numbers $A$ and $B$ ($1 \le A, B \le N$) of two people who are hostile to each other.

Hostility has no direction. The same pair can be given several times, and a line where $A$ equals $B$ can be given as well.

Print $1$ on one line if the theory can hold, and $0$ otherwise. If somebody is hostile to himself, the theory cannot hold.