BOJ 1154 팀 편성

void solve(){
    cin >> N;
    while(1){
        int u, v; cin >> u >> v;
        if(u == -1 && v == -1) break;
        know[u][v] = know[v][u] = true;
    }

    bool isBipartite = true;
    vector<int> color(N+1, 0);
    rep(i, 1, N+1) if(color[i] == 0){
        queue<int> Q;
        Q.push(i);
        color[i] = 1;
        while(!Q.empty()){
            int cur = Q.front(); Q.pop();
            rep(nxt, 1, N+1){
                if(cur == nxt) continue;
                if(know[cur][nxt]) continue;
                if(color[nxt] == 0){
                    color[nxt] = (color[cur] == 1 ? 2 : 1);
                    Q.push(nxt);
                }
                else if(color[nxt] == color[cur]){
                    isBipartite = false;
                    break;
                }
            }
        }
    }
    if(!isBipartite){
        cout << -1;
        return;
    }
    vector<int> team1, team2;
    rep(i, 1, N+1){
        if(color[i] == 1) team1.push_back(i);
        else team2.push_back(i);
    }

    cout << 1 << "\n";
    for(auto x: team1) cout << x << " "; cout << -1 << "\n";
    for(auto x: team2) cout << x << " "; cout << -1 << "\n";
}