The first line contains two integers $n$, $m$ ($1 \le n, m \le 10^6$) --- the number of friends and the number of conflicting relationships among friends.

The next $m$ lines contain two integers each, $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), indicating that friend $a_i$ conflicts with friend $b_i$.

It is guaranteed that no pair ($a;b$) is repeated more than once.