// 单链表模板
int head, e[N], ne[N], idx;

// 初始化
void init() {
    head = -1;
    idx = 0;
}

// 头插法
void insert_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

// 在第 k 个插入的数后插入一个数
void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

// 删除第 k 个插入的数后面的数
void remove(int k) {
    ne[k] = ne[ne[k]];
}

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

int head, e[N], ne[N], idx;

void init() {
    head = -1;
    idx = 0;
}

void insert_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

void remove(int k) {
    ne[k] = ne[ne[k]];
}

int main() {
    int m;
    cin >> m;
    init();
    while (m--) {
        char op;
        cin >> op;
        if (op == 'H') {
            int x;
            cin >> x;
            insert_to_head(x);
        } else if (op == 'D') {
            int k;
            cin >> k;
            if (k == 0) head = ne[head];
            else remove(k - 1); // 第k个插入的数下标是k-1
        } else {
            int k, x;
            cin >> k >> x;
            insert(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}

// 双链表模板
int e[N], l[N], r[N], idx;

// 初始化
void init() {
    // 0是头，1是尾
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在节点k的右边插入一个数x
void insert(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx++;
}

// 删除节点k
void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;

int e[N], l[N], r[N], idx;

void init() {
        //头结点指向尾结点，尾结点指向头节点，头结点指针为0，尾结点指针为1，所以头指针为1，尾指针为0
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

void insert(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;//必须这步在前面，否则r[k]的值会被修改 
    r[k] = idx++;
}

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main() {
    int m;
    cin >> m;
    init();
    while (m--) {
        string op;
        cin >> op;
        if (op == "L") {
            int x; cin >> x;
            insert(0, x); // 在头哨兵右边插入
        } else if (op == "R") {
            int x; cin >> x;
            insert(l[1], x); // 在尾哨兵左边插入
        } else if (op == "D") {
            int k; cin >> k;
            remove(k + 1); // 第k个插入的数下标是k+1
        } else if (op == "IL") {
            int k, x; cin >> k >> x;
            insert(l[k + 1], x);
        } else { // IR
            int k, x; cin >> k >> x;
            insert(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int l[N], e[N], r[N], add[N];
int idx;
void init() {
    r[0] = 1, l[1] = 0, idx = 2;
    add[0] = 0;
}
void insert_right(int k, int val) {
    e[idx] = val;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    add[++add[0]] = idx++;
}
void insert_left(int k, int val) {
    e[idx] = val;
    l[idx] = l[k];
    r[idx] = k;
    r[l[k]] = idx;
    l[k] = idx;
    add[++add[0]] = idx++;
}
void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
    e[k] = 0;
    add[0]--;
}
void printList() {
    for (int i = r[0]; i != 1; i = r[i]) {
        printf("%d ", e[i]);
    }
}
int main() {
    init();
    int n, k, p, m, x;
    scanf("%d", &n);
    insert_right(0, 1);
    for (int i = 2; i <= n; i++) {
        scanf("%d %d", &k, &p);
        if (p == 0) {
            insert_left(add[k], i);
        } else {
            insert_right(add[k], i);
        }
    }
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &x);
        if (e[add[x]] != 0) {
            remove(add[x]);
        }
    }
    printList();
    return 0;
}

// 数组模拟栈 (top指向栈顶元素)
int stk[N], top = -1;

// 入栈
stk[++top] = x;

// 出栈
top--;

// 查看栈顶
stk[top];

// 判空
if (top == -1) { /* 栈空 */ }

#include<iostream>
#include<string>
using namespace std;
const int N = 100010;

int stk[N], top = -1;

int main() {
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        if (s == "push") {
            int x;
            cin >> x;
            stk[++top] = x;
        } else if (s == "pop") {
            top--;
        } else if (s == "empty") {
            cout << (top == -1 ? "YES" : "NO") << endl;
        } else { // query
            cout << stk[top] << endl;
        }
    }
    return 0;
}

//模拟普通队列模板

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 tt >= hh，则表示不为空
if (tt >= hh)
{

}

//模拟循环队列模板

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空(其实不能这样简单判断是否为空)
if (hh != tt)
{

}

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];

//[hh, tt] 之间为队列（左闭右闭）
int hh = 0;//队头位置
int tt = -1;//队尾位置，存第一个元素时的索引为0，所以从0开始存储 
int m;
string s;


int main(){
    cin >> m;
    while(m--){
        cin >> s;
        //入队
        if(s == "push"){
            int x;
            cin >> x;
            q[++tt] = x;
        }
        //出队
        else if(s == "pop"){
            hh++;
        }
        //问空
        else if(s == "empty"){
            if(tt >= hh) cout << "NO" << endl;
    		else cout << "YES" << endl;
        }
        //查询 
        else if(s == "query"){
            cout << q[hh] << endl;
        }
    }
}

#include <iostream>
#include <stack>
#include <string>
#include <map>
using namespace std;

//双栈加优先级表 
stack<int> num;
stack<char> op;
map<char, int> h = { {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

//求值函数 
void eval()
{
    int b = num.top();//第二个操作数
    num.pop();

    int a = num.top();//第一个操作数
    num.pop();

    char p = op.top();//运算符
    op.pop();

    int r = 0;//结果 

    //计算结果
    if (p == '+') r = a + b;
    else if (p == '-') r = a - b;
    else if (p == '*') r = a * b;
    else if (p == '/') r = a / b;

    num.push(r);//结果入栈
}

int main()
{
    string s;//读入表达式
    cin >> s;

    for (int i = 0; i < s.size(); i++)
    {
    	char c = s[i]; 
    	//1.数字，数字入栈 
        if (isdigit(c))
        {	
        	//此while循环是在读到了数字时读完一整个数字 
            int x = 0, j = i;
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);
            i = j - 1;
        }
        //2.左括号，左括号无优先级，直接入栈
        else if (c == '(')//左括号入栈
        {
            op.push(c);
        }
        //3.右括号，括号特殊，遇到左括号直接入栈，遇到右括号不进栈，直接计算 
        else if (c == ')')
        {
            while(op.top() != '(')
                eval();
            op.pop();//左括号出栈
        }
        //4.运算符，主要是优先级的问题 
        else
        {
            while (op.size() && h[op.top()] >= h[c])//待入栈运算符优先级低，则先计算
                eval();
            op.push(c);//算完之后此运算符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算 
    cout << num.top() << endl;//输出结果
    return 0;
}

for (int i = 0; i < n; i++) {
    // 栈顶元素不满足条件(>=x)，则出栈
    while (top > -1 && stk[top] >= x) top--;
    if (top > -1) // 栈不空，栈顶就是答案
        result[i] = stk[top];
    else // 栈空，没有答案
        result[i] = -1;
    // 当前元素入栈
    stk[++top] = x;
}

#include <iostream>
using namespace std;
const int N = 100010;

int stk[N], top = -1;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // 当栈不空且栈顶元素大于等于x，则出栈
        while (top > -1 && stk[top] >= x) top--;
        // 此时栈顶即为左侧第一个比x小的数
        if (top > -1) cout << stk[top] << " ";
        else cout << -1 << " ";
        // 当前元素x入栈
        stk[++top] = x;
    }
    cout << endl;
    return 0;
}

int hh = 0, tt = -1;
for (int i = 0; i < n; i++) {
    // 1. 判断队头是否滑出窗口
    if (hh <= tt && q[hh] < i - k + 1) hh++;
    // 2. 维护队列单调性，从队尾移除 >= 当前元素的
    while (hh <= tt && a[q[tt]] >= a[i]) tt--;
    // 3. 当前元素下标入队
    q[++tt] = i;
    // 4. 形成窗口后，输出队头（最值）
    if (i >= k - 1) cout << a[q[hh]] << " ";
}

#include <iostream>
using namespace std;
const int N = 1000010;

int a[N], q[N]; // q存的是下标

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    // 求窗口最小值
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) cout << a[q[hh]] << " ";
    }
    cout << endl;

    // 求窗口最大值
    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k - 1) cout << a[q[hh]] << " ";
    }
    cout << endl;
    return 0;
}

#include <deque>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int n, k;
const int N = 1e6 + 5;
int nums[N];
class MonotonicMaxQueue {
public:
    deque<int> que;
    void pop(int val) {
        if (!que.empty() && que.front() == val) {
            que.pop_front();
        }
    }
    int getMaxVal() { return que.front(); }
    void push(int val) {
        while (!que.empty() && que.back() < val) {
            que.pop_back();
        }
        que.emplace_back(val);
    }
};
class MonotonicMinQueue {
public:
    deque<int> que;
    void pop(int val) {
        if (!que.empty() && que.front() == val) {
            que.pop_front();
        }
    }
    int getMaxVal() { return que.front(); }
    void push(int val) {
        while (!que.empty() && que.back() > val) {
            que.pop_back();
        }
        que.emplace_back(val);
    }
};
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    vector<int> result;
    //  最小值
    MonotonicMinQueue mqMin;
    for (int i = 0; i < k; i++) {
        mqMin.push(nums[i]);
    }
    printf("%d ", mqMin.getMaxVal());
    for (int i = k; i < n; i++) {
        mqMin.pop(nums[i - k]);
        mqMin.push(nums[i]);
        printf("%d ", mqMin.getMaxVal());
    }
    printf("\n");
    //  最大值
    MonotonicMaxQueue mqMax;
    for (int i = 0; i < k; i++) {
        mqMax.push(nums[i]);
    }
    printf("%d ", mqMax.getMaxVal());
    for (int i = k; i < n; i++) {
        mqMax.pop(nums[i - k]);
        mqMax.push(nums[i]);
        printf("%d ", mqMax.getMaxVal());
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;

char p[N], s[M];
int ne[N];

int main() {
    int n, m;
    cin >> n >> (p + 1) >> m >> (s + 1);

    // 求next数组
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    // kmp匹配
    for (int i = 1, j = 0; i <= m; i++) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n) {
            cout << i - n << " "; // 题目要求0-indexed
            j = ne[j];
        }
    }
    cout << endl;
    return 0;
}

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的字符串数量

// 插入
void insert(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

// 查询
int query(char *str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

//Trie树快速存储字符集合和快速查询字符集合
#include <iostream>
using namespace std;
const int N = 100010;
//son[][]存储子节点的位置，也存储第几个结点（idx的值），分支最多26条；
//cnt[p]存储以p节点结尾的字符串个数（同时也起标记作用）
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str) {
    int p = 0;  //类似指针，指向当前节点
    for(int i = 0; str[i]; i++){
        int u = str[i] - 'a'; //将字母转化为数字
        if(!son[p][u]) son[p][u] = ++idx;   //该节点不存在，创建节点
        p = son[p][u];  //使“p指针”指向下一个节点
    }
    cnt[p]++;  //结束时的标记，也是记录以此节点结束的字符串个数
}

int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u];
    }
    return cnt[p];  //返回字符串出现的次数
}

int main() {
    int m;
    cin >> m;
    while (m--) {
        char op[2];
		cin>>op>>str; 
        if(*op == 'I') insert(str);
        else cout<<query(str)<<endl;
        //改成char op; op == 'I'也行
    }
    return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 31 * N;

int a[N];
int son[M][2], idx; // 01-Trie

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int search(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (son[p][!u]) { // 贪心：走相反的路
            p = son[p][!u];
            res = res * 2 + !u;
        } else {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return x ^ res; // 返回异或值
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = max(res, search(a[i]));
    }
    cout << res << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 5, M = 3e6 + 5;
int a[N];
int son[M][2], idx;
// 将当前的x插入Trie树中
void insert(int x) {
  int p = 0;
  for (int i = 30; ~i; i--) {
    int& s = son[p][x >> i & 1];
    if (!s) {
      s = ++idx;  // 创建新节点
    }
    p = s;
  }
}
// 查找当前Trie树中和 x 异或最大的结果
int query(int x) {
  int res = 0;
  int p = 0;
  for (int i = 30; ~i; i--) {
    int t = x >> i & 1;
    if (son[p][!t]) {
      res += 1 << i;
      p = son[p][!t];
    } else {
      p = son[p][t];
    }
  }
  return res;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    insert(a[i]);
  }
  int res = 0;
  for (int i = 0; i < n; i++) { res = max(res, query(a[i])); }
  printf("%d", res);
  return 0;
}

int p[N]; // p[x] 表示 x 的父节点

// 返回x的根节点 + 路径压缩
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 合并a和b所在的集合
p[find(a)] = find(b);

#include<iostream>

using namespace std;

const int N=100010;
int p[N];//存储父节点的数组，p[x]=y表示x的父节点为y 

//找根节点（集合编号）的函数 ，查找过一遍后所有经过的x的父节点的父节点都会变为集合编号以降低时间复杂度 
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);//只有根节点的p[x]=x，所以要一直找直到找到根节点 
    return p[x];//找到了便返回根节点的值
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;//刚开始每个数自成一个集合，每个数自己为根节点 
    while(m--)
    {
        char op;
        int a,b;
        cin>>op>>a>>b;
        if(op=='M') p[find(a)]=find(b);//集合合并操作(把a合并到b集合)
        else{
        	if(find(a)==find(b)) cout<<"Yes"<<endl;//如果根节点一样,就输出yes
	        else cout<<"No"<<endl;
		}
    }
    return 0;
}

#include <iostream>

using namespace std;

const int N = 100010;

//只有根节点的s能代表集合的节点数量，所以s中括号里一般都要有find函数先找出根节点
int p[N], s[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        s[i] = 1;
    }
    while (m--) {
        string op;
        int a, b;
        cin >> op;
        if (op == "C") {
            cin >> a >> b;
            if (find(a) == find(b)) continue;
            s[find(b)] += s[find(a)]; //先加size
            p[find(a)] = find(b);//再连
        } else if (op == "Q1") {
            cin >> a >> b;
            if (find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else {
            cin >> a;
            cout << s[find(a)] << endl;
        }
    }
    return 0;
}

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1e5 + 5;

// p[i] 表示节点 i 的父节点（并查集的父指针）
// sz[i] 表示以 i 为根的集合大小（仅对根节点有效）
int p[N], sz[N];

// 初始化：每个节点单独成集合，父节点指向自己，大小为 1
void init() {
  for (int i = 0; i < N; i++) {
    p[i] = i;  // 初始父节点为自己
  }
  // 将 sz 数组全部填充为 1（每个单独节点的集合大小为 1）
  fill(sz, sz + N, 1);
}

// 查找函数（带路径压缩）：返回节点 x 的根节点
// 同时把沿途节点直接挂到根上，以加速后续查询
int find(int x) {
  if (x == p[x]) {
    return x;  // x 本身就是根
  } else {
    // 递归查找并压缩路径
    return p[x] = find(p[x]);
  }
}

int main() {
  // op 用于存储操作类型字符串，比如 "C"、"Q1"、"Q2"
  char op[5];
  init();
  int n, m, a, b;
  scanf("%d%d", &n, &m);

  while (m--) {
    scanf("%s", op);

    if (op[0] == 'C') {
      // 合并操作：C a b
      // 把 a 所在集合合并到 b 所在集合（不使用按秩合并，仅把 a 的根接到 b
      // 的根）
      scanf("%d%d", &a, &b);
      a = find(a);
      b = find(b);
      if (a == b) {
        // 已经在同一集合中，直接跳过
        continue;
      } else {
        // 先把 b 的集合大小增加 a 的集合大小
        sz[b] += sz[a];
        // 再把 a 的根指向 b 的根（合并）
        p[a] = b;
      }

    } else if (op[1] == '1') {
      // 查询连通性：Q1 a b（注意 op[1] == '1' 用来判断是否为 Q1）
      scanf("%d%d", &a, &b);
      a = find(a);
      b = find(b);
      if (a == b) {
        printf("Yes\n");
      } else {
        printf("No\n");
      }

    } else {
      // 查询集合大小：Q2 a
      // 读取 a，输出 a 所在集合的大小（通过 sz[find(a)] 获得根节点的大小）
      scanf("%d", &a);
      printf("%d\n", sz[find(a)]);
    }
  }
  return 0;
}

#include <iostream>

using namespace std;

const int N = 50010;

//d[x]表示x到父节点的距离，p[x]表示x的父节点
int p[N], d[N];

/*int find(int x)函数两个作作用：
1.使根节点成为x的父节点，并返回x的根节点
2.将d[x]即x到父节点的距离变为x到根节点的距离*/
int find(int x) {
    if (p[x] != x) {
        int t = find(p[x]);
        //find完之后，p[x]直接连接根节点了，d[p[x]]是x的父节点p[x]到根节点的距离，即：
        /*x到根节点的距离 = x到父节点的距离 + 父节点到根节点的距离
        d[x] = d[x] + d[p[x]];*/
        //如果不先find那么d[p[x]]就是x的父节点p[x]到父节点的距离，就不一定是p[x]到根节点的距离，即：
        /*x到根节点的距离 = x到父节点的距离 + 父节点到父节点的距离
        d[x] = d[x] + d[p[x]];*/
        //因为find完之后p[x]的子节点就是x，父节点就是根节点0
        d[x] += d[p[x]];//这步进行完d[x]是没错的了，就是x到根节点的总距离
        //这步再把x的父节点改为根节点，取代之前x和根节点之间的父节点，这样x和根节点就是距离也没错也是直接连接的了
        p[x] = t;
    }
    return p[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    int res = 0;
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;
        //1.X或Y比N大，假话
        if ( x > n || y > n) res++;
        else {
            //为什么px一定要等于py也就是x和y为什么一定要在一个集合内呢
            //如果不在同一个集合内，就无法正确地模拟食物链的关系。因为在同一个集合内，才能通过距离数组 d 来维护元素之间的食物链关系，并查集核心思想也是要在一个集合内
            int px = find(x), py = find(y);
            if (t == 1) { //此时t == 1，表示已经告诉我们x和y是同类
                //在一个树上并且x和y不是同类即(d[x] - d[y])%3余1或余2，假话+1
                if (px == py &&
                        (d[x] - d[y]) % 3) res++; //注意此时已经经过了find函数所以d[x]是x到根节点的距离
                else if (px !=
                         py) { //当x和y不在一个集合内时把他们合并，注意if条件不要漏，不要直接else，是只有x和y不在一个集合时才要合并
                    p[px] = py;
                    d[px] = d[y] - d[x];//1式
                }
            } else { //此时告诉我们x吃y
                //在一个树上并且x不吃y即(d[x] - d[y] - 1)%3不等于0，假话+1
                if (px == py && (d[x] - d[y] - 1) % 3) res++;
                else if (px !=
                         py) { //当x和y不在一个集合内时把他们合并，注意if条件不要漏，不要直接else，是只有x和y不在一个集合时才要合并
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x]; //2式，1式和2式具体思路看图
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}