#include <vector>
const int MAXN = 100 * 1000 + 10;
     
bool mark[MAXN];
bool color[MAXN];
vector <int> adj[MAXN];
    
// اگر خروجی تابع ۱ باشد یعنی مؤلفه‌ی v دو‌بخشی است و اگر ۰ باشد یعنی دور فرد دارد.
bool dfs(int v, bool c){
    mark[v] = 1;
    color[v] = c;
    for(int i=0; i<adj[v].size(); i++) {
            int u = adj[v][i];
            if(mrk[u] != 1)
            {
                bool ret = dfs(u, 1-c);  //  با رنگ مخالف وارد رأس همسایه میشویم
                if (ret == 0)
                    return 0;
            }
            
            if(color[u] == c)  //  اگر رنگ همسایه همرنگ این رأس بود
                return 0;
        }
    }
    return 1;
}