#include "ezici.h"
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<long long> par, sz;
    DSU(long long n){ 
        par.resize(n+1);
        sz.resize(n+1);
        for(long long i=1; i<=n; i++) {par[i]=i; sz[i]=1;}
    }
    long long findpar(long long k) { 
        if(par[k]==k) return k;
        return par[k] = findpar(par[k]);
    }
    void join(long long a, long long b){
        a=findpar(a); b=findpar(b);
        if(a==b) return;
        if(sz[a]<sz[b]) swap(a,b);
        par[b]=a;
        sz[a]+=sz[b];
    }
};

bool task1(int N, int M, vector<pair<pair<int, int>, bool>> v) {
    DSU dsu(N*2+20);
    for(auto e : v) {
        long long x = e.first.first, y = e.first.second, t = e.second;
        if(t==1) {
            dsu.join(x, y);
            dsu.join(x+N, y+N);
        }
        else {
            dsu.join(x, y+N);
            dsu.join(x+N, y);
        }
    }
    for(long long i = 1; i <= N; i++) {
        if(dsu.findpar(i)==dsu.findpar(i+N)) return 0;
    }
    return 1;
}
int used[200000];
int depth[200000];
vector<int> v[200000];
void dfs(int i) {
    for(auto x : v[i]) {
        depth[x]=depth[i]+1;
        dfs(x);
    }
}
long long task2(vector<long long> p) {
    for(int i = 0; i < p.size(); i++) {
        v[p[i]].push_back(i+2);
    }
    dfs(1);
    int mx=0;
    for(int i = 1; i <= p.size()+1; i++) mx=max(mx, depth[i]);
    return mx;
}
long long task3(vector<long long> a) {
    return *max_element(a.begin(), a.end())-*min_element(a.begin(), a.end());
}
long long task4(vector<long long> a) {
    long long odd=0,even=0;
    for(auto x : a) {
        if(x%2==0) even++;
        else odd++;
    }
    return odd*(odd-1)/2+even*(even-1)/2;
}
long long task5(vector<long long> a) {
    long long even=0;
    for(auto x : a)even+=x%2==0;
    return even;
}
long long task6(vector<long long> a) {
    long long mx=-1e18-1,ans=0;
    for(auto &x : a) {
        if(x>mx) ans++;
        mx=max(mx,x);
    }
    return ans;
}
long long task7(vector<long long> a) {
    unordered_set<long long> s;
    for(auto &x : a) s.insert(x);
    return s.size();
}
vector<long long> task8(vector<long long> a) {
    unordered_map<long long, int> last;
    long long n = a.size();
    last[0]=-1;
    long long sum=0;
    for(int i = 0; i < n; i++) {
        sum+=a[i];
        sum%=n;
        if(last.find(sum)!=last.end()) {
            vector<long long> ans;
            for(int j = last[sum]+1; j <= i; j++) {
                ans.push_back(j);
            }
            return ans;
        }
        last[sum]=i;
    }
    return {};
}

long long task9(vector<long long> a) {
    long long mn=0, sum=0, ans=-1e18;
    for(int i = 0; i < a.size(); i++) {
        sum+=a[i];
        ans=max(ans, sum-mn);
        mn=min(mn, sum);
    }
    return ans;
}

long long task10(vector<long long> a) {
    long long ans=0;
    for(auto &x : a) ans^=x;
    return ans;
}