void print_out(node *cur);// 输出节点

node *find_prev(node *cur);// 寻找前驱节点

void morris(node *root) {
  node *cur = root;
  while (cur != NULL) {// 没有遍历完
    if (cur->left == NULL) {// 1: cur没有左子节点
      print_out(cur);
      cur = cur->right;
    } else {
      node *prev = find_prev(cur);
      if (prev->right == NULL) {// 2.1: prev没有右子节点
        prev->right = cur;// 修改树结构
        cur = cur->left
      } else if (prev->right == cur) {// 2.2: prev的右子节点为cur
        prev->right = NULL;// 恢复树结构
        print_out(cur);
        cur = cur->right;
      } else {
        assert(0);
      }
    }
  }
}

void dfs(node u) {
  u.visit = 1;
  for (int i = 0; i < u.adj.size(); i ++) {
    node v = u.adj[i];
    if (v.visit == 0) {
      dfs(v);
    }
  }
}

void bfs() {
  q.push(s);
  while (q.empty() == 0) {
    node u = q.top();
    q.pop();
    for (int i = 0; i < u.adj.size(); i ++) {
      node v = u.adj[i];
      if (v.visit == 0) {
        v.depth = u.depth + 1;
        q.push(v);
      }
    }
  }
}

void tarjan(int x) {
  s.push(x);
  depth ++;
  dfn[x] = depth;// dfs标记
  low[x] = depth;// tarjan标记
  in_stack[x] = 1;// 是否入栈
  int u, v;
  for (int i = 0; i < near[x].size(); i ++) {
    int v = near[x][i].v;
    if (dfn[v] == 0) {// 未被标记过
      tarjan(v);
      low[x] = my_min(low[x], low[v]);
    } else if (in_stack[v] == 1) {// 已经入栈
      low[x] = my_min(low[x], dfn[v]);// my_min(low[x], low[v])l
    }
  }

  if (dfn[x] == low[x]) {// 强连通分量
    block ++;// 连通块数目
    while (s.empty() == 0) {
      v = s.top();
      in_stack[v] = 0;
      s.pop();
      if (v == x) break;
    }
  }
}

struct path {
  public:
    int u;// 起点
    int v;// 终点
    int c;// 容量
    int f;// 流量
    int back;// 反向边编号

    path() {
      f = 0;
    }
};
int T, n, m;
int path_num;
int s, t;
int level[MAXN];// 分层
vector<int> near[MAXN];// 邻接表
path paths[MAXM];// 所有edge

void add_path(int u, int v, int c) {
  // 正向边
  paths[path_num].u = u;
  paths[path_num].v = v;
  paths[path_num].c = c;
  paths[path_num].f = 0;
  paths[path_num].back = path_num + 1;
  near[u].push_back(path_num);
  path_num ++;
  // 反向边
  paths[path_num].u = v;
  paths[path_num].v = u;
  paths[path_num].c = 0;
  paths[path_num].f = 0;
  paths[path_num].back = path_num - 1;
  near[v].push_back(path_num);
  path_num ++;
}

int dfs(int x, int flow) {
  if (x == t) return flow;
  int total_flow = 0;
  for (int i = 0; i < near[x].size(); i ++) {
    int forward = near[x][i];
    int v = paths[forward].v;
    int w = paths[forward].c - paths[forward].f;
    if (w > 0 && level[v] == level[x] + 1) {
      int extend = dfs(v, my_min(w, flow - total_flow));
      if (extend > 0) {
        int backward = paths[forward].back;
        paths[forward].f += extend;
        paths[backward].f -= extend;
        total_flow += extend;
      }
    }
  }
  return total_flow;
}

int bfs() {
  queue<int> que;
  memset(level, 0, sizeof(level));
  que.push(s);
  level[s] = 1;
  while (que.empty() == 0) {
    int u = que.front();
    que.pop();
    for (int i = 0; i < near[u].size(); i ++) {
      int forward = near[u][i];
      int v = paths[forward].v;
      int w = paths[forward].c - paths[forward].f;
      if (w > 0 && level[v] == 0) {
        level[v] = level[u] + 1;
        que.push(v);
      }
    }
  }
  return level[t];
}

int dinic() {
  int ans = 0;
  while (1) {
    if (bfs() == 0) break;// 没有增广路
    ans += dfs(s, INF);
  }
  return ans;
}

vector<int> x_near[];// x的邻接表
int y_match[];// y的配对记录
int y_visit[];// 用于dfs的标记

void match() {
  for (int i = 0; i < n; i ++) {// n为x个数
    memset(y_visit, 0, sizeof(y_visit));
    if (dfs(i)) {
      ans ++;
    }
  }
}

int dfs(int x) {
  for (int i = 0; i < x_near[x].size(); i ++) {
    int index = x_near[x][i];
    if (y_visit[index] == 0) {// 没有被dfs过的y
      y_visit[index] = 1;
      if (y_match[index] == -1 || dfs(y_match[index])) {
        // 如果 (没有配对 || 已经配对的能够增广)
        y_match[index] = x;// 为x找到新的配对
        return 1;
      }
    }
  }
  return 0;
}

int n;// 总数
int x_ex[MAXN];// x的期望
int y_ex[MAXN];// y的期望
int x_visit[MAXN];// 每轮配对时x的标记
int y_visit[MAXN];// 每轮配对时y的标记
int y_match[MAXN];// 与y配对的x
int y_slack[MAXN];// 每轮遍历x改变的期望
int near[MAXN][MAXN];// 邻接矩阵

int KM();
int dfs(int x);

int dfs(int x) {
  assert(x > 0);
  x_visit[x] = 1;
  for (int i = 1; i <= n; i ++) {
    if (y_visit[i] == 0) {
      int gap = x_ex[x] + y_ex[i] - near[x][i];// 两者的期望和与实际值之差
      if (gap == 0) {
        // 符合要求
        y_visit[i] = 1;// TODO
        if (y_match[i] == 0 || dfs(y_match[i])) {
          // 没有匹配 || 可以增广
          y_match[i] = x;
          return 1;
        }
      } else {
        y_slack[i] = my_min(y_slack[i], gap);
      }
    }
  }
  return 0;
}

int KM() {
  memset(x_ex, 0, sizeof(x_ex));
  memset(y_ex, 0, sizeof(y_ex));// 无期望
  memset(y_match, 0, sizeof(y_match));// 无配对

  // 最大化x期望
  for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= n; j ++) {
      x_ex[i] = my_max(x_ex[i], near[i][j]);
    }
  }

  // 为每个x进行匹配
  for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= n; j ++) {// 初始期望为无穷
      y_slack[j] = INF;
    }

    while (1) {// 直到找到配对为止
      memset(x_visit, 0, sizeof(x_visit));
      memset(y_visit, 0, sizeof(y_visit));

      int extend = dfs(i);
      if (extend == 1) break;

      // 找出最小的slack
      int min_slack = INF;
      for (int j = 1; j <= n; j ++) {
        if (y_visit[j] == 0) {// 不符合要求的y(交错树之外)
          min_slack = my_min(min_slack, y_slack[j]);
        }
      }

      // 调整x, y的期望
      for (int j = 1; j <= n; j ++) {
        if (x_visit[j] == 1) {
          x_ex[j] -= min_slack;
        }
        if (y_visit[j] == 1) {
          y_ex[j] += min_slack;
        } 
      }
    }
  }

  // 计算和
  int ans = 0;
  for (int i = 1; i <= n; i ++) {
    ans += near[y_match[i]][i];
  }

  return ans;
}

void kmp() {// a[1], b[1]为起始项
  // 计算前缀表
  p_len = 0;
  for (int i = 2; i <= m; i ++) {// 注意初始赋值
    while (p_len && b[p_len + 1] != b[i]) {
      p_len = kmp[p_len];
    }
    if (b[p_len + 1] == b[i]) {
      p_len ++;
      kmp[i] = p_len;
    }
  }
  // 进行匹配
  p_len = 0;
  for (int i = 1; i <= n; i ++) {// 注意初始赋值
    while (p_len && b[p_len + 1] != a[i]) {
      p_len = kmp[p_len];
    }
    if (b[p_len + 1] == a[i]) {
      p_len ++;
      if (p_len == m) {
        printf("%d\n", i - p_len + 1);
        break;
      }
    }
  }
}