试除法判定质数 —— 模板题 AcWing 866. 试除法判定质数
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
试除法分解质因数 —— 模板题 AcWing 867. 分解质因数
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
朴素筛法求素数 —— 模板题 AcWing 868. 筛质数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i; j <= n; j += i)
            st[j] = true;
    }
}
线性筛法求素数 —— 模板题 AcWing 868. 筛质数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
约数个数和约数之和 —— 模板题 AcWing 870. 约数个数, AcWing 871. 约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
欧几里得算法 —— 模板题 AcWing 872. 最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
求欧拉函数 —— 模板题 AcWing 873. 欧拉函数
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}
筛法求欧拉函数 —— 模板题 AcWing 874. 筛法求欧拉函数
int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}
快速幂 —— 模板题 AcWing 875. 快速幂
求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
扩展欧几里得算法 —— 模板题 AcWing 877. 扩展欧几里得算法
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}
高斯消元 —— 模板题 AcWing 883. 高斯消元解线性方程组
// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前上的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}
递归法求组合数 —— 模板题 AcWing 885. 求组合数 I
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
通过预处理逆元的方式求组合数 —— 模板题 AcWing 886. 求组合数 II
首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p)    // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
    fact[i] = (LL)fact[i - 1] * i % mod;
    infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
Lucas定理 —— 模板题 AcWing 887. 求组合数 III
若p是质数，则对于任意整数 1 <= m <= n，有：
    C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k)       // 快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int C(int a, int b)     // 通过定理求组合数C(a, b)
{
    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    return res;
}


int lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
    1. 筛法求出范围内的所有质数
    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
    3. 用高精度乘法将所有质因子相乘

int primes[N], cnt;     // 存储所有质数
int sum[N];     // 存储每个质数的次数
bool st[N];     // 存储每个数是否已被筛掉


void get_primes(int n)      // 线性筛法求素数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p)       // 求n！中的次数
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)       // 高精度乘低精度模板
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

get_primes(a);  // 预处理范围内的所有质数

for (int i = 0; i < cnt; i ++ )     // 求每个质因数的次数
{
    int p = primes[i];
    sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )     // 用高精度乘法将所有质因子相乘
    for (int j = 0; j < sum[i]; j ++ )
        res = mul(res, primes[i]);

卡特兰数 —— 模板题 AcWing 889. 满足条件的01序列
给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)
NIM游戏 —— 模板题 AcWing 891. Nim游戏
给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0

公平组合游戏ICG
若一个游戏满足：

由两名玩家交替行动；
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S

SG函数
在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

有向图游戏的和 —— 模板题 AcWing 893. 集合-Nim游戏
设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

//st表 nlong n , 查询区间最大值;
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
inline int read()//快读板
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int Max[MAXN][21];
int Query(int l,int r)
{
    int k=log2(r-l+1); 
    return max(Max[l][k],Max[r-(1<<k)+1][k]);//把拆出来的区间分别取最值 
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    int N=read(),M=read();
    for(int i=1;i<=N;i++) Max[i][0]=read();
    for(int j=1;j<=21;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)//注意这里要控制边界 
            Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);//如果看不懂边界的话建议好好看看图 
    for(int i=1;i<=M;i++)
    {
        int l=read(),r=read();
        printf("%d\n",Query(l,r));
    }
    return 0;
}

//c++时间控制在10^7 - 10^8
n <= 30 :  指数级别, dfs+剪枝，状态压缩dp
n <= 100 : => O( n^3 ) : floyd，dp，高斯消元
n <= 1000 :=> O( n ^ 2) O(logn*n*2) :dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n <= 10000 :=> O( n * sprt(n)) 块状链表、分块、莫队
n <= 100000: => O(n*logn) :各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
n <= 1000000: => O(n) : 以及常数较小的 O(nlogn)算法 => 单调队列、 hash、双指针扫描、BFS、并查集，kmp、AC自动机，常数比较小的 O(nlogn)的做法：sort、树状数组、heap、dijkstra、spfa
n <= 10^7 => O(n) :双指针扫描、kmp、AC自动机、线性筛素数
n <= 10^9 => O(sprt(n)) :判断质数
n <= 10^18 => O( log n ) :最大公约数，快速幂，数位DP
n <= 10^1000 = > O((log n)^2) 高精度加减乘除
n <=10^100000 => O( logk * loglogk) k表示位数，高精度加减、FFT/NTT.

// 01背包问题
 for(int i = 1; i <=n; ++i) {
        for(int j = V ; j >= v[i]; --j) {//从i-1转移，使f[j-v[i]]是上一个i-1的状态，故j从大到小枚举.
            f[j] = max(f[j],f[j-v[i]] + w[i]);
        }
    }

//完全背包问题
 for(int i = 1 ;i <= n; ++i) {
        for(int j = v[i]; j <= V; ++j) {//变化之数，位于f[i-1][j-v],要已知f[i-1][j-v] ,从j小状态到大状态,j = 0-v
              f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
//多重背包问题
  for(int i = 1 ;i <= n; ++i) {
        for(int j = 0; j <= V; ++j) {
            for(int k =0 ; j - k*v[i]>=0&&k<=s[i]; ++k) {
                f[i][j] = max(f[i-1][j-k*v[i]]+w[i]*k,f[i][j]);
            }
        }
    }
//多重背包问题 II ->二进制的完全背包
for(int i = 1; i <=n; ++i) {
        cin>>a>>b>>c;//c个
        int t = 1;
        while(t <= c){
            cut++;
            v[cut] = t*a;
            w[cut] = t*b;
            c-=t;
            t = t+ t;
        }
        if(c>0) {
            cut++;
            v[cut] = c*a;
            w[cut] = c*b;
        }
    }
    n = cut;
    for(int i = 1; i <= n; ++i) {
    for(int j = V; j >= v[i]; --j) {
        f[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    }
//分组背包问题
//f(i,j) 前i组选，<=j体积，的最大价值
for(int i = 1;i <= n; ++i) {
        for(int j = 0; j <= V; ++j)
        for(int k = 0; k <= s[i]; ++k) {
            if(j-v[i][k]>=0)
            f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[n][V];
// 数字三角形
 memset(f,-0x3f,sizeof(f));
    f[1][1] = a[1][1];
    for(int i = 1;i <=n ;++i) {
        for(int j = 1;j <=i; ++j) {
            if(j-1<1&&i-1>=1){
                f[i][j] = f[i-1][j] + a[i][j];
            }
            else if(i-1>=1&&j-1>=1)
            f[i][j] = max(f[i-1][j-1],f[i-1][j])+a[i][j];

        }
    }
    int ans = -0x3f3f3f3f;
    for(int i =1 ;i <=n ; ++i) {
        ans = max(ans,f[n][i]);
    }
//最长上升子序列
  for(int i = 1; i <= n; ++i) f[i]=1;
    for(int i = 2; i <= n; ++i) {
        for(int j = i-1; j >= 1; --j) {
            if(a[i]>a[j])
            f[i] = max(f[j]+1,f[i]);
        }
    }
    int ans = -0x3f3f3f3f;
    for(int i = 1; i <= n ;++i) {
        ans = max(ans,f[i]);
    }
//最长上升子序列 II
  for(int i = 1; i <= n; ++i) cin>>a[i];
    q.push_back(a[1]);
    for(int i =2; i <= n; ++i) {
        if(a[i]>q.back()) {
            q.push_back(a[i]);
        }
        else {
            *lower_bound(q.begin(),q.end(),a[i]) = a[i]; 
        }
    }
    cout<<q.size();
//最长公共子序列
//f[i][j]，a中前i的子序列，和b中前j的子序列的最长公共长为f[i][j] ;
//对它第a[i],和b[j],选与不选进行分类
// 00 （==f[i-1][j-1]） 01（+00 =f[i-1][j]） 10(+00 =f[i][j-1]) 11(f[i-1][j-1] + 1);
 for(int i = 1; i<= n; ++i)
    for(int j = 1; j <= m; ++j) {
        f[i][j] = max(f[i-1][j],f[i][j-1]);
        if(a[i]==b[j]) {
            f[i][j] = max(f[i][j],f[i-1][j-1]+1);
        }
    }
//最短编辑距离
//f[i][j]:指a1-i变成1-j的最小步数
//对第ai有3种操作即
//1删除：f[i][j] = f[i-1][j] + 1;
//2添加(在i后添加了b[j]): f[i][j] = f[i][j-1] + 1;
//3替换 ： f[i][j] = f[i-1][j-1] + 1/0(a[i] ~= b[j]);
//注意边界的初始化
for(int i =1; i <= N; ++i) {
        f[i][0] = i;
        f[0][i] = i;
    }
    for(int i = 1;i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            f[i][j] = min(f[i-1][j],f[i][j-1]) + 1;
            if(a[i] == b[j]) f[i][j] = min(f[i-1][j-1],f[i][j]);
            else f[i][j] = min(f[i-1][j-1]+1,f[i][j]);
        }
    }
//石子合并
//f[i][j] -- > 将第i个到第j个合并的最小值；len = j - i + 1;
//f[i][j] = f[i][k] + f[k+1][j] + s[j] - s[i-1]; k = i -- j-1;
//f[i][j]min - > f[i][k] - > 从小推大
   for(int i = 1;i <= n; ++i) {
       cin>>s[i];
       s[i] += s[i-1];
   } 
   for(int len = 2; len <= n; ++len) {
       for(int i = 1;i +len -1<= n ; ++i) {
           int l = i,r = l + len -1;
           f[l][r] = 1e8;
           for(int k = i; k <= r-1; ++k) {
               f[l][r] = min(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]);
           }
       }
   }
   cout<<f[1][n];
//整数划分 : n = n1 + n2 ..
//1完全背包
//f(i,j) 选 1 - i 恰好凑到j的最大数量
// f[i-1][j] + f[i-1][j-i] + 1 + ...f[i-1][j-k*i];
// f(i,j-i) =  f[i-1][j-i]  f[i-1][j-i] + 1 + ..;
//f[i][j] = f[i-1][j]  +  f[i][j-i];
int main() {
    cin>>n;
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i) f[i][0] =1;
    for(int i = 1 ;i <= n; ++i) {
        for(int j = 1; j<= n; ++j) {
            if(j-i>=0)
            f[i][j] = (f[i-1][j]+f[i][j-i])%mod;
            else 
            f[i][j] = f[i-1][j]%mod;
        }
    }
    cout<<f[n][n]%mod;
}
//计数问题
//count(n,x) -- >第1-n中的x数
//tttxttt; -> 1 ttt*10^3;
//tttxttt; - 》 2 x>xx ->1000;
//3 x == xx -> ttt+1;
//4 x < xx -> 0;
int get(vector<int> v,int r,int l) {
    int res = 0;
    while(r>=l){
        res = res*10 + v[r];
        r--; 
    }

    return res;
}
int count(int n,int x) {
    if(!n) return 0;
    vector<int> v;
    while(n) {
        v.push_back(n%10);
        n/=10;
    }
    int len = v.size();
    int ans = 0;
    for(int i = len - 1 - !x; i >=0; --i) {
        if(i < len - 1) {
            ans += get(v,len - 1,i + 1)*pow(10,i);
            if(!x) ans -=pow(10,i);
        }
        if(v[i] == x) {
            ans += get(v,i-1,0) + 1;
        }
        else if(v[i]>x) {
            ans +=pow(10,i);
        }
    }
    return ans;
}
//最短Hamilton路径 1-n
//f[i][j] = f[i_k][k] + g[k][j];
#include<bits/stdc++.h>
using namespace std;
const int N = 21;
int f[1<<N][N],n,g[N][N];

int main() {
    cin>>n;
    for(int i =0;i < n; ++i) {
        for(int j = 0; j<n; ++j) cin>>g[i][j];
    }
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;
    for(int i = 0; i < 1<<n; ++i) {
        for(int j = 0;j < n; ++j) {
            if(i>>j&1)
            for(int k = 0;k < n ; k++) {
                if((i-(1<<j))>>k&1)
                f[i][j] = min(f[i-(1<<j)][k] + g[k][j],f[i][j]);
            }
        }
    }
    cout<<f[(1<<n)-1][n-1];
}
//没有上司的舞会
//f[i][0] 指从以i为根不选i的最大值总和，f[i][1]选i总和
//f[i][0] = max(f[s][0],f[s][1]);
#include<iostream>
using namespace std;
const int N = 6005;
int e[2*N],ne[2*N],h[N],idx;
int n,H[N],l,k,f[N][2];
bool v[N];
void add(int v,int u) {
    idx++;
    e[idx] = v,ne[idx] = h[u],h[u] = idx;
}
int dfs(int u){
    f[u][1] = H[u];
    for(int i = h[u];i!=0;i=ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][1],f[j][0]);
        f[u][1] += f[j][0];
    }
    return max(f[u][0],f[u][1]);
}
int main() {
    cin>>n;
    for(int i = 1; i<= n; ++i) cin>>H[i];

    while(n--!=1) {
        cin>>l>>k;
        add(l,k);
        v[l] = 1;
    }
    int t= 1,root = 1;
    while(v[t]) t++;
    root = t;

    cout<<dfs(root);
}