
ZOJ Problem Set  4052
DreamGrid has $n$ friends which are conveniently numbered from $1$ to $n$. They can be divided into two groups (possibly empty) such that:
Now, given the pairs of friends who know each other, DreamGrid would like to know the number of ways to find a group of friends with maximum size such that every pair of friends in the group have to know each other, and he would also like to know the number of ways to find a group of friends with maximum size such that every pair of friends in the group must not know each other. InputThere are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains two integers $n$ and $m$ $(1 \le n \le 10^5, 0 \le m \le 10^5)$  the number of friends and the number of pairs of friends who know each other. The $i$th of the following $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n, a_i \ne b_i$), which denotes that the $a_i$th friend and the $b_i$th friend know each other. Note that every unordered pair of ($a, b$) will appear at most once. It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $2 \times 10^6$. OutputFor each test case, output two integers separated by a single space. The first integer indicates the number of ways to find a group of friends with maximum size such that every pair of friends in the this group have to know each other. The second integer indicates the number of ways to find a group of friends with maximum size such that every pair of friends in the group must not know each other. Sample Input3 3 2 1 2 2 3 6 6 1 2 2 3 1 3 1 4 2 5 3 6 4 1 1 2 Sample Output2 1 1 4 1 2 Author: ZHANG, Yong Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 