Chi-sensei

#include<stdio.h>
#include<vector>
using namespace std;
typedef long long int ll;
int n,m;
vector<int> adj[2010];
int color[2010];
int const mod = 1e9+7;
bool dfs(int u,int c){
    if(color[u] != 0){
        return color[u] == c;
    }
    color[u] = c;
    for(int i=0;i<adj[u].size();i++){
        int v = adj[u][i];
        if(!dfs(v, c == 1 ? 2 : 1)){
            return false;
        }
    }
    return true;
}


int main()
{
    scanf("%d %d",&n,&m);

    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int T;
    scanf("%d",&T);

    int cntcom = 0;
    bool isbipartite = true;
    for(int i=1;i<=n;i++){
        if(color[i] == 0){
            cntcom++;
            if(!dfs(i,1)){
                isbipartite = false;
                break;
            }
        }
    }

    if(T == 1){
        printf("%s",(isbipartite ? "Yes" : "No"));
    }
    else if(T == 2){
        if(isbipartite){
            printf("%s\n",(isbipartite ? "Yes" : "No"));
            for(int i=1;i<=n;i++){
                if(color[i] == 1){
                    printf("%d ",i);
                }
            }
            printf("\n");
            for(int i=1;i<=n;i++){
                if(color[i] == 2){
                    printf("%d ",i);
                }
            }
        }
        else{
            printf("%s\n",(isbipartite ? "Yes" : "No"));
        }

    }
    else{
        if(isbipartite){
            ll ans = 1;
            for(int i=1;i<=cntcom;i++){
                ans = ((ans % mod) * (2 % mod))%mod;
            }
            printf("%lld",ans);
        }
        else{
            printf("0");
        }
    }

    return 0;
}