#include <bits/stdc++.h>

using namespace std;

bool findDoublet(vector<vector<int> >& dislikes, int a, int b){
    vector<vector<int> >::iterator it;
    for(it = dislikes.begin(); it != dislikes.end(); it++){
        vector<int>::iterator itr;
        itr = it->begin();
        if(*itr == a){
            itr++;
            if(*itr == b)
                return true;
        }
    }
    return false;
}

bool DFS(int k, int n, vector<vector<int> >& dislikes, int visited[], int color){
    visited[k] = color;
    for(int i = k + 1; i <= n; i++){
        if(findDoublet(dislikes, k, i)){
            if(visited[i]){
                if(visited[i] % 2 == color % 2)
                    return false;
            }
            else{
                bool result = DFS(i, n, dislikes, visited, color + 1);
                if(result == false)
                    return false;
            }
        }
    }

    return true;
}

bool possibleBipartition(int n, vector<vector<int> >& dislikes) {
    if(n == 1)
        return true;

    int visited[n + 1];
    for(int i = 1; i <= n; i++)
        visited[i] = 0;

    for(int i = 1; i < n; i++){
        int color = visited[i] ? visited[i] : 0;
        if(!DFS(i, n, dislikes, visited, color))
            return false;
    }
    return true;
}

int main()
{
    int n = 3;
    vector<vector<int> > dislikes;
    vector<int> dislike;
    dislike.push_back(1);
    dislike.push_back(2);
    dislikes.push_back(dislike);
    cout << possibleBipartition(n, dislikes);

    return 0;
}