#include <bits/stdc++.h>
#include "ezici.h"
using namespace std;
const int maxn = 1e5 + 7;
vector<pair<int, bool>> g[maxn];
vector<int> g2[maxn];
int c[maxn];
bool visited[maxn];
int pos[maxn];
bool stop = false;
void dfs(int u, bool dali)
{
    if (stop)
        return;
    c[u] = dali;
    visited[u] = true;
    for (auto v : g[u])
    {
        int x = v.first;
        bool t = v.second;
        if (t == 0)
        {
            if (!visited[x])
                dfs(x, !dali);
            else
            {
                if (c[x] == c[u])
                {
                    stop = true;
                    return;
                }
            }
        }
        else
        {
            if (!visited[x])
                dfs(x, dali);
            else
            {
                if (c[x] != c[u])
                {
                    stop = true;
                    return;
                }
            }
        }
    }
}
int maxi = 0;
void dfs2(int u, int par, int br)
{
    maxi = max(maxi, br);
    for (auto x : g2[u])
    {
        if (x != par)
            dfs2(x, u, br + 1);
    }
}

bool task1(int N, int M, std::vector<std::pair<std::pair<int, int>, bool>> v)
{
    for (auto x : v)
    {
        int a = x.first.first;
        int b = x.first.second;
        bool t = x.second;
        g[a].push_back({b, t});
        g[b].push_back({a, t});
    }
    for (int i = 1; i <= N; i++)
    {
        if (!visited[i])
            dfs(i, false);
    }
    return !stop;
}
long long task2(vector<long long> p)
{
    int N = p.size() + 1;
    for (int i = 2; i <= N; i++)
    {
        g2[p[i - 2]].push_back(i);
        g2[i].push_back(p[i - 2]);
    }
    dfs2(1, -1, 0);
    return maxi;
}
long long task3(vector<long long> a)
{
    long long int mini = LLONG_MAX;
    long long int maxi2 = LLONG_MIN;
    for (auto x : a)
    {
        mini = min(mini, x);
        maxi2 = max(maxi2, x);
    }
    return maxi2 - mini;
}
long long task4(vector<long long> a)
{
    long long int breven = 0;
    long long int brodd = 0;
    for (auto x : a)
    {
        if (x % 2 == 0)
            breven++;
        else
            brodd++;
    }
    long long int ans = 0;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] % 2 == 0)
        {
            breven--;
            ans += breven;
        }
        else
        {
            brodd--;
            ans += brodd;
        }
    }
    return ans;
}
long long task5(vector<long long> a)
{
    long long int br = 0;
    for (auto x : a)
    {
        if (x % 2 == 0)
            br++;
    }
    return br;
}
long long task6(std::vector<long long> a)
{
    long long int maxi = LLONG_MIN;
    long long int br = 0;
    for (auto x : a)
    {
        if (x > maxi)
            br++;
        maxi = max(maxi, x);
    }
    return br;
}

long long task7(std::vector<long long> a)
{
    unordered_set<long long> s;
    for (auto x : a)
        s.insert(x);
    return s.size();
}

std::vector<long long> task8(std::vector<long long> a)
{
    long long sum = 0;
    int i = 1;
    vector<long long> ans;
    pos[0] = 0;
    for (auto x : a)
    {
        sum += x;
        sum %= a.size();
        if (pos[sum] != 0)
        {

            for (int j = pos[sum]; j < i; j++)
            {
                ans.push_back(j);
            }
            return ans;
        }
        pos[sum] = i;
        i++;
    }
    return {};
}

long long task9(std::vector<long long> a)
{
    long long maxi = LLONG_MIN;
    long long minpref = 0;
    long long sum = 0;
    for (auto x : a)
    {
        sum += x;
        maxi = max(maxi, sum - minpref);
        minpref = min(minpref, sum);
    }
    return maxi;
}

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