/*
 * 顾名思义：二指针即使用两个指针进行遍历，两层循环
 * - 内层循环右指针 j 不断贪心，直到求得从下标 i 开始满足条件的最优值
 * - 外层循环左指针 i 缓慢向前移动
 *
 * 比如给定一个字符串，求不重复元素的最大区间
 *
 * 示例：
 *
 *  a b c d a e f
 * ij
 *
 *  i       j        abcd = 4
 *    i         j  bcdaef = 6
 *             ij
 */

#include <stdio.h>
#include <string.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define N 100

int get_max(char *s) {
    int len = strlen(s);
    int ans = 0;
    int vis[256] = {0};
    for (int i = 0, j = 0; i < len; i++) {
        while (j < len && !vis[s[j]]) {
            vis[s[j++]] = 1;
        }
        ans = max(ans, j - i);
        vis[s[i]] = 0;
    }
    return ans;
}

int main () {
    char s[] = "abcdaef";
    printf("%d\n", get_max(s));
    return 0;
}

/*
 * 插入排序
 *
 * 时间复杂度O(n^2)，空间复杂度O(1)，稳定排序
 * 将数组划分为有序区和无序区，然后每趟从无序区中取出元素插入有序区即可，每趟归位一个元素
 *
 * 举例：
 *
 *     i
 * 1 | 8 2 9 5 7 6 3 4
 *
 *       i
 * 1 8 | 2 9 5 7 6 3 4
 *
 *         i
 * 1 2 8 | 9 5 7 6 3 4
 *
 *           i
 * 1 2 8 9 | 5 7 6 3 4
 *
 *             i
 * 1 2 5 8 9 | 7 6 3 4
 */

#include <stdio.h>

void insert_sort(int data[], int n) {
    for (int i = 1; i < n; i++) { // 从第 2 个元素开始往有序区插入(单个元素肯定有序)
        int tmp = data[i];        // 当前待插入的元素
        int j = i - 1;
        while (j >= 0 && tmp < data[j]) { // 往前遍历有序区，寻找插入位置
            data[j + 1] = data[j];        // 如果待插入元素小于当前元素，则将当前元素往后移一位
            j--;
        }
        data[j + 1] = tmp; // 插入到指定位置
    }
}

int main() {
    int a[] = {1, 8, 2, 9, 5, 7, 6, 3, 4};
    insert_sort(a, 9);
    for (int i = 0; i < 9; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

/*
 * 快速排序
 *
 * 不稳定排序
 * 平均时间复杂度可证明为：O(N * logN)，最差时间复杂度：O(N^2)
 * 空间复杂度：O(1)，若考虑栈最好情况为为：O(logN)，最差为：O(N)
 * 复杂度分析：http://blog.csdn.net/hn_gsf/article/details/52249621
 */

#include <stdio.h>

void swap(int *data, int l, int r) {
    int t = data[l];
    data[l] = data[r];
    data[r] = t;
}

/*
 * 实现方式 1
 *
 * 思想：每次在待排序区间 [l, r] 选定一个基准值 data[x]，将比 data[x] 小的数放在 data[x] 左边，比 data[x] 大的数放在右边，经过处理后 data[x] 的位置就唯一了，其下标记为 m，然后递归处理区间 [l, m-1]、[m+1, r]
 * 实现：每次使用两个指针 i=l, j=r，循环处理，j-- 向左，当找到比 data[x] 小的数将其交换到左边，i++ 向右，当找到比 data[i] 大的数将其交换到右边，当 i=j 时即满足 data[l..i-1] < data[i=j] < data[j+1..r]
 *
 * 在最优情况下，递归深度为 logN 层，每层处理的时间复杂度为 O(N)，即总复杂度为 O(N * logN)
 * 在最差情况下，即待排序数组为正序或倒序时，需要递归 n-1 层，即每次划分的时候只单向移动一个单位，即分治退化成链，每层需要比较 n-i 次，总时间复杂度为 O(N^2)
 *
 * 举例：
 *
 * 取 data[x]=data[l]=5
 *
 * l               r
 * i               j
 * 5 9 8 2 4 7 1 3 6
 *
 * i             j    <=
 * 5 9 8 2 4 7 1 3 6
 * 3 9 8 2 4 7 1 5 6  找到第一个比 5 小的数 3，交换 3 到左边
 *
 *   i           j    =>
 * 3 9 8 2 4 7 1 5 6
 * 3 5 8 2 4 7 1 9 6  找到第一个比 5 大的数 9，交换 9 到右边
 *
 *   i         j      <=
 * 3 5 8 2 4 7 1 9 6
 * 3 1 8 2 4 7 5 9 6  找到第一个比 5 小的数 1，交换 1 到左边
 *
 *     i       j      =>
 * 3 1 8 2 4 7 5 9 6
 * 3 1 5 2 4 7 8 9 6  找到第一个比 5 大的数 8，交换 8 到右边
 *
 *     i   j          <=
 * 3 1 5 2 4 7 8 9 6
 * 3 1 4 2 5 7 8 9 6  找到第一个比 5 小的数 4，交换 4 到左边
 *
 *         ij
 * 3 1 4 2 5 7 8 9 6
 *
 * 具体实现上有点细微的区别，每次交换的数都是 data[x]，所以并不需要真正交换，直接赋值即可，最后将 i=j 处赋值回 data[x] 即可：
 *
 * l               r
 * i               j
 * 5 9 8 2 4 7 1 3 6
 *
 * i             j
 * 3 9 8 2 4 7 1 _ 6
 *
 *   i           j
 * 3 _ 8 2 4 7 1 9 6
 *
 *   i         j
 * 3 1 8 2 4 7 _ 9 6
 *
 *     i       j
 * 3 1 _ 2 4 7 8 9 6
 *
 *     i   j
 * 3 1 4 2 _ 7 8 9 6
 *
 *         ji
 * 3 1 4 2 5 7 8 9 6
 *
 * 最差时间复杂度举例：
 *
 * l               r
 * i               j
 * 1 2 3 4 5 6 7 8 9
 *
 *   i             j
 *   2 3 4 5 6 7 8 9
 *
 *     i           j
 *     3 4 5 6 7 8 9
 *
 * ...
 *
 */
void quick_sort_1(int *data, int l, int r) {
    if (l < r) {
        // 此处可随机基准值防止最坏情况：交换 l 和后面某个位置的值
        // int pivot = (l + r) >> 1;
        // swap(data, l, pivot);

        int i = l, j = r, tmp = data[l];
        while (i != j) {
            while (j > i && data[j] >= tmp) j--; // 右边如果比基准值大，则不需要交换，j 继续向左
            data[i] = data[j];                   // 找到第一个需要交换的 j，交换到左边
            while (i < j && data[i] <= tmp) i++; // 左边如果比基准值小，则不需要交换，i 继续向右
            data[j] = data[i];                   // 找到第一个需要交换的 i，交换到右边
        }
        data[i] = tmp;
        quick_sort_1(data, l, i - 1);
        quick_sort_1(data, i + 1, r);
    }
}

/*
 * 实现方式 2
 *
 * 实现 1 中其实是直接与基准值本身进行交换，比如：[5] 1 8 2 3 6 => 3 1 8 2 [5] 6 => 3 1 [5] 2 8 6 => 3 1 2 [5] 8 6
 *
 * 这里不同的循环将左边比基准值大的数和右边比基准值小的数进行交换，循环结束时除了基准值外满足排序要求，且此时 i=j 指向从右往左第一个比基准值小的数，于是将其和基准值交换即使得满足最终要求
 *
 * 举例：
 *
 * l               r
 * i               j
 * 5 9 8 2 4 7 1 3 6
 *
 *   i           j
 * 5 9 8 2 4 7 1 3 6  从右到左找到第一个比 5 小的数 3，从左到右找到第一个比 5 大的数，将两者进行交换
 * 5 3 8 2 4 7 1 9 6
 *
 *     i       j
 * 5 3 8 2 4 7 1 9 6
 * 5 3 1 2 4 7 8 9 6
 *
 *         ij
 * 5 3 1 2 4 7 8 9 6  循环停止时的序列，i=j，4 < 5，所以直接将 5 和 data[ij] 交换
 * 4 3 1 2 5 7 8 9 6
 */
void quick_sort_2(int data[], int l, int r) {
    if (l < r) {
        int i = l, j = r, tmp = data[l];
        while (i < j) {
            while (j > i && data[j] >= tmp) j--; // 不需要交换，j 继续向左
            while (i < j && data[i] <= tmp) i++; // 不需要交换，i 继续向右
            if (i != j) {                        // 交换
                int t = data[i];
                data[i] = data[j];
                data[j] = t;
            }
        }
        swap(data, l, i); // 最后将基准值换到 i=j 处使得满足最终条件
        quick_sort_2(data, l, i - 1);
        quick_sort_2(data, i + 1, r);
    }
}

/*
 * 实现方式 3，实现起来更简单
 *
 * 思想和方式 2 差不多，不同的时在实现上只需要用一个指针从左到右处理，遇到右边有比基准值更小的数则挨着基准值依次交换到左边，最后将基准值同最后一个比基准值小的数进行交换达到排序要求
 *
 * 举例：
 *
 * l i             r
 * 5 9 8 2 4 7 1 3 6
 *
 * l     i
 * 5 9 8 2 4 7 1 3 6  遇到一个比 5 小的数 2，交换到左边
 * 5 2 8 9 4 7 1 3 6
 *   la  i
 *
 * l la    i
 * 5 2 8 9 4 7 1 3 6  遇到一个比 5 小的数 4，依次交换到左边
 * 5 2 4 9 8 7 1 3 6
 *     la
 *
 * l   la      i
 * 5 2 4 9 8 7 1 3 6  遇到一个比 5 小的数 1，依次交换到左边
 * 5 2 4 1 8 7 9 3 6
 *       la
 *
 * l     la      i
 * 5 2 4 1 8 7 9 3 6  遇到一个比 5 小的数 3，依次交换到左边
 * 5 2 4 1 3 7 9 8 6
 *         la
 *
 * l       la      i
 * 5 2 4 1 3 7 9 8 6  last 表示比基准值小的上一个数，所以这里将其和基准值交换
 * 3 2 4 1 5 7 9 8 6
 */
void quick_sort_3(int data[], int l, int r) {
    if (l < r) {
        int last = l;
        for (int i = l + 1; i <= r; i++) { // 从左向右处理
            if (data[i] < data[l]) {       // 遇到右边有比基准值更小的数则挨着基准值依次交换到左边
                swap(data, ++last, i);
            }
        }
        swap(data, l, last); // 与基准值交换
        quick_sort_3(data, l, last - 1);
        quick_sort_3(data, last + 1, r);
    }
}

/*
 * 利用快排的思想查找第 k 大或前 k 大
 * 平均复杂度：O(n)
 *
 * 第 k 大，倒序排序
 * 第 k 小，正序排序
 */
int find_kth(int data[], int l, int r, int k) {
    if (l < r) {
        int i = l, j = r, tmp = data[l];
        while (i != j) {
            while (j > i && data[j] <= tmp) j--;
            data[i] = data[j];
            while (i < j && data[i] >= tmp) i++;
            data[j] = data[i];
        }
        data[i] = tmp;
        if (k == i) return data[i];                         // 如果 data[i] 最终就在第 k 个数处
        else if (k < i) return find_kth(data, l, i - 1, k); // 如果在左边，递归处理左边
        else return find_kth(data, i + 1, r, k);            // 如果在右边，递归处理右边
    }
    return -1; // unreachable
}

void test_quick_sort_1() {
    int a[] = {5, 9, 8, 2, 4, 7, 1, 3, 6};
    quick_sort_1(a, 0, 8);
    for (int i = 0; i < 8; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void test_quick_sort_2() {
    int a[] = {5, 9, 8, 2, 4, 7, 1, 3, 6};
    quick_sort_2(a, 0, 8);
    for (int i = 0; i < 8; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void test_quick_sort_3() {
    int a[] = {5, 9, 8, 2, 4, 7, 1, 3, 6};
    quick_sort_3(a, 0, 8);
    for (int i = 0; i < 8; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void test_find_kth() {
    int a[] = {5, 9, 8, 2, 4, 7, 1, 3, 6};
    int ret = find_kth(a, 0, 8, 2); // 这里下标从 0 开始，定义第 0 大为 9，第 1 大为 8，第 2 大为 7...
    printf("%d\n", ret);
}

int main() {
    test_quick_sort_1();
    test_quick_sort_2();
    test_quick_sort_3();
    test_find_kth();
    return 0;
}

/*
 * 堆
 *
 * 最大堆：父节点 > 左右儿子
 * 最小堆：父节点 < 左右儿子
 *
 * 注意：堆不一定都是完全二叉树，只要满足节点和子节点的大小关系的二叉树就是堆，完全二叉树对应的堆叫做二叉堆，因此可直接用数组实现
 * 先利用已有元素构建的堆是一棵完全二叉树(后续的都是 push、pop，不能随机插入子节点，不影响平衡性)，因此显然平衡，复杂度为：O(logN)
 *
 * 主要操作：(前两种为内部逻辑，服务于插入、删除等操作)
 * 上浮
 * 下沉
 *
 * 初始化
 * 插入
 * 删除
 */

#include <stdio.h>
#define N 10010

struct Heap {
    int size;    // 元素个数
    int data[N]; // 堆元素，此处为最小堆

    // 举例：
    //
    //        97 76 65 49 50 27 38 13
    // 第一趟：97 76 65 13 50 27 38 49 <= 调整49所在节点
    // 第二趟：97 76 27 13 50 65 38 49 <= 调整65所在节点
    // 第三趟：97 13 27 49 50 65 38 76 <= 调整76所在节点
    // 第四趟：13 49 27 76 50 65 38 97 <= 调整97所在节点
    void build(int a[], int n) {
        size = n;
        for (int i = 0; i < size; i++) {
            data[i] = a[i];
        }

        // 根据已有数据构造堆，复杂度为：O(n)
        // 参考：http://blog.csdn.net/leosha/article/details/46116959
        // 从最后一个非叶子节点开始调整(叶子节点没必须再往下调整，已经是底端了)，因为下标从 0 开始所以 -1
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i, size);
            print();
        }
    }

    // 向下调整
    // 下标从 0 开始的左右儿子下标为 2 * rt + 1、2 * rt + 2
    // 下标从 1 开始其实更简单，可以同线段树写为 2 * rt、2 * rt + 1
    void down(int rt, int sz) {
        int l = rt << 1 | 1;
        int r = l + 1;
        if (l >= sz) l = rt;
        if (r >= sz) r = rt; // trick，如果超出范围了不算取 rt 本身就行了

        // 此处为最小堆，如果子节点更小，交换子节点，继续向下调整，使其满足父节点 < 子节点
        // 举例：
        //     9           5         5
        //    / \   =>    / \   =>  / \
        //   5  6        9  6      7  6
        //  / \         / \       / \
        // 7  8        7  8      9  8
        int mi = data[l] < data[r] ? l : r;
        if (data[mi] < data[rt]) {
            swap(mi, rt);
            down(mi, sz);
        }
    }

    // 向上调整
    // 添加元素时先将元素放到末尾，然后向上调整，使其满足堆的性质
    void up(int rt) {
        while (1) {
            // 得到父节点，当下标从 1 开始时 p = rt / 2
            // 如果到根节点了或已经满足父节点 < 子节点时停止向上调整
            // 举例：
            //     5         5         5         2
            //    / \       / \       / \       / \
            //   7  6  =>  7  6  =>  7  2  =>  7  5
            //  / \       / \ /     / \ /     / \ /
            // 9  8      9  8 2    9  8 6    9  8 6
            int p = (rt - 1) >> 1;
            if (p == rt || data[p] <= data[rt]) break;
            swap(p, rt);
            rt = p;
        }
    }

    // 添加元素
    // 添加到末尾，从 0 开始，下标为 size - 1，然后向上调整
    void push(int c) {
        data[size++] = c;
        up(size - 1);
    }

    // 添加元素到固定容量的堆中，用于计算 topN，比如最小堆可用来计算最大的 N 个元素
    // 先判断元素个数，如果小于堆容量，则直接将元素添加到堆尾，然后向上调整堆
    // 否则和堆顶元素判断
    //   如果比堆顶元素还小，则直接丢弃
    //   否则将堆顶元素赋值为当前值，然后向下调整堆
    void push_2(int c) {
        if (c <= data[0]) return;
        data[0] = c;
        down(0, size);
    }

    // 弹出堆顶元素(最小值)
    // 将最后一个元素赋值到堆顶，然后向下调整
    // 举例：
    //     5         8        6
    //    / \       / \      / \
    //   7  6  =>  7  6  => 7  8
    //  / \       /        /
    // 9  8      9        9
    int pop() {
        int c = data[0];
        data[0] = data[--size];
        down(0, size);
        return c;
    }

    // 堆排序，复杂度：O(nlogn)，空间复杂度：O(1)，不稳定排序
    // 不断地交换堆顶元素到堆的最后一个元素，然后向下调整即可
    // 由于是最小堆，交换后最后的元素最小，为倒序排序
    // 注意这里是原地排序，会破坏堆的结构
    void sort() {
        int sz = size;
        while (sz >= 1) {
            swap(0, --sz);
            down(0, sz);
        }
    }

    void swap(int i, int j) {
        int t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    void print() {
        for (int i = 0; i < size; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
    }

};

int main() {
    int a[] = {97, 76, 65, 49, 50, 27, 38, 13};
    struct Heap h;
    h.build(a, 8);            // 利用已知数据构建堆
    h.push(20);               // 添加新的元素
    h.print();
    printf("%d\n", h.pop());  // 最小值出堆：13
    h.print();
    h.push_2(56);             // 添加新的元素，同时保持元素总数不变，这里 56 进 27 出
    h.print();
    h.sort();                 // 堆排序
    h.print();
    return 0;
}

/* 
 * 置换原理解释：原状态与目标状态形成一个置换群
 *
 * 比如：
 * 2 1 6 5 3 4
 * 1 2 6 3 4 5
 *
 * 得到置换群，其循环节为 3：
 * 2 1   6   5 3 4
 * 1 2   6   3 4 5
 *
 * 显然要从原状态得到目标状态，只需要在每个置换内部交换，这样交换次数才最少，因为置换之间交换是没有意义的
 * 置换内交换有两种方法：
 *
 * 比如：
 * 3 4 2 1 5 7 6 => 1 2 3 4 5 6 7
 *
 * 第一种方法，从左到右，每次归位当前位置的元素：
 * 1 的位置不是 1，而是 3，于是 1 和 3 交换，得到：1 4 2 3 7 6 5     归位 1
 * 2 的位置不是 2，而是 4，于是 2 和 4 交换，得到：1 2 4 3 7 6 5     归位 2
 * 3 的位置不是 3，而是 4，于是 3 和 4 交换，得到：1 2 3 4 7 6 5     归位 3、4，(1 2 3 4) 属于一个置换，置换内排序完成
 * ..
 * 5 的位置就是 5，不变                                           (5) 属于一个置换
 * 6 的位置不是 6，而是 7，于是 6 和 7 交换，得到：1 2 3 4 5 6 7     (6 7) 属于一个置换，置换内排序完成
 * 共交换 4 次，每次归位一个元素
 *
 * 第二种方法，从左到右，每次归位当前位置值的元素：
 * 1 的位置不是 1，而是 3，于是 3 和 a[3] 交换，得到：2 4 3 1 5 7 6  归位 3
 * 1 的位置不是 1，而是 2，于是 2 和 a[2] 交换，得到：4 2 3 1 5 7 6  归位 2
 * 1 的位置不是 1，而是 4，于是 4 和 a[4] 交换，得到：1 2 3 4 5 7 6  归位 4、1，(1 2 3 4) 属于一个置换，置换内排序完成
 * ..
 * 5 的位置就是 5，不变                                           (5) 属于一个置换
 * 6 的位置不是 6，而是 7，于是 7 和 a[7] 交换，得到：1 2 3 4 5 6 7  (6 7) 属于一个置换，置换内排序完成
 * 共交换 4 次，每次归位一个元素，复杂度：O(N)
 */

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define N 10010

int n;
int a[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            while (a[i] != i) { // 置换群，形成环，多次交换
                swap(a[i], a[a[i]]);
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define min(a, b) ((a) < (b) ? (a) : (b))
#define N 1010
#define M 1010

int ans;
int n, m;
int sx, sy;
int ex, ey;
char mpt[N][M];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

void dfs(int x, int y, int step) {
    if (x == ex && y == ey) { // 终点
        ans = min(ans, step);
        return;
    }
    if (step >= ans) return; // 超过当前最小步数，剪枝
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m && mpt[tx][ty] != '#') {
            char t = mpt[tx][ty];
            mpt[tx][ty] = '#';     // 标记为墙，避免重复访问，这里也可以单独使用一个 vis 数组用于标记
            dfs(tx, ty, step + 1); // 递归搜索
            mpt[tx][ty] = t;       // 回溯，尝试另外的路径
        }
    }
}

/*
 * 5 5
 * S-###
 * -----
 * ##---
 * E#---
 * ---##
 */
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", mpt[i]);
        for (int j = 0; j < m; j++) {
            if (mpt[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (mpt[i][j] == 'E') {
                ex = i;
                ey = j;
            }
        }
    }
    ans = n * m - 1;
    dfs(sx, sy, 0);
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 1010
#define M 1010

struct Node {
    int x, y, d;
};

struct Queue {
    int front, rear;
    Node nodes[N];
};

int n, m;
int sx, sy;
int ex, ey;
char mpt[N][M];
bool vis[N][M];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

// 使用 STL 实现
int bfs() {
    queue<Node> q;
    Node now, next;
    now.x = sx;
    now.y = sy;
    now.d = 0;
    vis[sx][sy] = 1;
    q.push(now); // 起点进队
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (now.x == ex && now.y == ey) { // 到达终点，返回
            return now.d;
        }
        for (int i = 0; i < 4; i++) {
            next = now;
            next.x += dir[i][0];
            next.y += dir[i][1];
            next.d++;
            if (next.x >= 0 && next.x < n && next.y >=0 && next.y < m && mpt[next.x][next.y] != '#' && !vis[next.x][next.y]) {
                vis[next.x][next.y] = 1;
                q.push(next);             // 进队下个节点
            }
        }
    }
    return -1; // 无法到达终点
}

// 使用数组实现
// 记录层数的两种方式：
// - 在每个节点中记录当前层数
// - 使用两个变量记录每层节点的数量
// - 使用两层循环，内层循环每次出队 q.size() 次，即将当前层的节点全部出队，将下一层节点进队
int bfs_2() {
    Queue q;
    Node now, next;
    memset(vis, 0, sizeof(vis));
    int now_step_num = 1, next_step_num = 0, step = 0;

    now.x = sx;
    now.y = sy;
    now.d = 0;
    vis[sx][sy] = 1;
    q.front = q.rear = 0;
    q.nodes[++q.rear] = now; // 起点进队
    while (q.front != q.rear) {
        now = q.nodes[++q.front]; // 出队
        // printf(">>> now: %d %d %d %d\n", now.x, now.y, now.d, step);
        if (now.x == ex && now.y == ey) {
            return now.d;
        }
        for (int i = 0; i < 4; i++) {
            next = now;
            next.x += dir[i][0];
            next.y += dir[i][1];
            next.d++;
            if (next.x >= 0 && next.x < n && next.y >=0 && next.y < m && mpt[next.x][next.y] != '#' && !vis[next.x][next.y]) {
                vis[next.x][next.y] = 1;
                q.nodes[++q.rear] = next; // 入队
                next_step_num++;
            }
        }
        now_step_num--;
        if (now_step_num == 0) { // 若当前层出队完了，换到下一层，下一层从 0 计数
            now_step_num = next_step_num;
            next_step_num = 0;
            step++;
        }
    }
    return -1; // 无法到达终点
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", mpt[i]);
        for (int j = 0; j < m; j++) {
            if (mpt[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (mpt[i][j] == 'E') {
                ex = i;
                ey = j;
            }
        }
    }
    printf("%d\n", bfs());
    printf("%d\n", bfs_2());
    return 0;
}

/*
 * 记忆化：在搜索中，往往会重复搜索，因此可以使用一个数组记录下来，防止重复搜索。记忆化很多时候可以很方便地改写为动态规划
 * 
 * 下面用最简单的斐波拉契举例，可以看出两者差异是巨大的
 */

#include <stdio.h>
#include <time.h>
#define MAXN 50
#define LL long long

// 1 2 3 4 5 6 7
// 1 1 2 3 5 8 13 ...
LL fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

LL dp[MAXN];
LL fibonacci_2(int n) {
    if (dp[n]) return dp[n];
    if (n == 1 || n == 2) return dp[n] = 1;
    return dp[n] = fibonacci_2(n - 1) + fibonacci_2(n - 2);
}

int main() {
    int n = 40;
    int t1 = clock();
    int ans1 = fibonacci(n);
    int t2 = clock();
    int ans2 = fibonacci_2(n);
    int t3 = clock();
    printf("ans1 = %d, used %d ms\n",ans1, (t2 - t1));
    printf("ans2 = %d, used %d ms\n",ans1, (t3 - t2));
    return 0;
}

/*
 * 有 N 物品，每件物品都有一定的价值、同时会占用一定的空间，问容量为 s 的背包最最多能装下价值为多少的物品？
 *
 * 二维形式
 *
 * dp[i][j] 表示将前 i 件物品放入容量为 j 的背包可获得的最大价值，这里先都假设不必刚好装满
 *
 * 状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) if j >= w[i]
 */

#include <iostream>
using namespace std;
#define N 110

int w[N];
int v[N];
int dp[N][N];

int main() {
    int n, s;
    cin >> s >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i <= n; i++)
        cin >> v[i];

    for (int i = 1; i <= n; i++) // n 件物品
        for (int j = 0; j <= s; j++) { // 容量小于 s
            if (w[i] <= j) // 第 i 件物品能放下
                dp[i][j] = _cpp_max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]); // 取放或不放的最大价值
            else // 放不下
                dp[i][j] = dp[i - 1][j]; // 取前 i - 1 件物品放入容量为 j 的背包的最大价值
        }
    cout << dp[n][s] << endl; // 输出前 n 件物品放入容量为 s 的背包的最大价值
    return 0;
}

/*
 * 一维形式
 *
 * 在上面的实现中，1 2..n 件物品中所有的状态都保存下来了，其实没有必要，我们最终只需要得到前 n 件物品产生的最大价值
 * 空间优化：使用 dp[j] 代替 dp[i][j]，不需要每轮循环的状态数据都进行保留，只要保证当 i = n，使用 dp[j](当轮赋值) 时 dp[j - ..](上轮的值)存在即可，故 j = s、j >= 0 需要倒序
 *
 * dp[j] 表示把物品放入容量为j背包的最大价值
 * 状态转移方程：dp[j] = max(dp[j], dp[j - w[i]] + v[i]) if j >= w[i]
 */

#include <iostream>
using namespace std;
#define N 110

int w[N];
int v[N];
int dp[N];

int main() {
    int n, s;
    cin >> s >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 1; i <= n; i++)
        cin >> v[i];

    for (int i = 1; i <= n; i++) { // 枚举每一个物品，然后更新每一个背包的最大价值
        for (int j = s; j >= w[i]; j--) { // 枚举能放下的背包状态，更新这些背包的最大价值，一层层更新，相当于把每一个容量的背包的最大价值得到了，容量大的背包需要建立在容量小的背包的基础上，而最后我们只需要容量为 S 的背包的最大价值
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 取放与不放的最大价值，此 dp[j - w[i]] 实质上是表示的是 i - 1 循环时的状态数据
        }
    }
    cout << dp[s] << endl; // 输出放入容量为 s 的最大物品价值
    return 0;
}

/*
 * 在某些情况下，要求背包必须刚好装满
 *
 * 状态转移过程是一样的，不同的地方在于初始化：
 * 之前，我们对 dp 整个数组初始化为 0，表示容量为 i 的背包能装下物品的最大价值为 0，在递推过程中，对于每件物品，可以选择放或不放，最终背包不一样刚好被装满
 * 现在，初始化 dp[0] = 0，其它元素为 -INF，表示除了容量为 0 的背包初始价值为 0，其他状态的背包都未定义，在递推过程中，某些状态的背包如果只依赖这些不存在的状态，即这些状态也会变为未定义 -INF，最终我们可以通过判断 dp[s] 是否小于 0 即可
 */

// 字典树：顾名思义，就是一棵像字典一样的树
// 字典树可用于高效查找字符串或字符串前缀，时间复杂度：O(n)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000010
#define M 26

int sz;       // sz 表示待分配的字典树节点下标
int ch[N][M]; // ch 用于存储字典树，如 ch[2][3] 表示字典树中第 2 个节点的第 3 个子节点
int val[N];   // val 用于存储字典树对应节点的附属信息

// 初始化字典树
// 0 为根节点，一个虚拟的空节点
void init() {
    // memset(ch[0], 0, sizeof(ch[0]));
    sz = 1;
}

int get_id(char c) { return c - 'a'; }

// 插入新的串到树中
void insert(char *s) {
    int p = 0;
    int l = strlen(s);
    for (int i = 0; i < l; i++) { // 依次遍历字符串，从根节点开始，如果不存在即新建节点
        int id = get_id(s[i]);
        if (!ch[p][id]) {
            ch[p][id] = sz++;
        }
        p = ch[p][id];
        val[p]++; // 以 s[0..i] 为前缀的字符串出现次数+1
    }
}

// 在树中查找前缀串
int find(char *s) {
    int p = 0;
    int l = strlen(s);
    for (int i = 0; i < l; i++) {
        int id = get_id(s[i]);
        if (!ch[p][id]) return 0; // 不存在
        p = ch[p][id];
    }
    return val[p]; // 返回指定前缀串出现的次数
}

/*
 * abc
 * abcde
 * qwer
 *
 * a
 * abc
 * abcde
 * empty
 */
int main() {
    char s[12];
    init();
    while (gets(s), strlen(s)) {
        insert(s);
    }
    while (gets(s)) {
        cout << find(s) << endl;
    }
    return 0;
}

/*
 * 线段树-单点更新
 *
 * 线段树是一种完全二叉树：除最后一层的节点可能只存在左子树，上层为满二叉树
 * 因此可直接使用数组实现，满足：节点 rt 的子节点为 rt * 2、rt * 2 + 1(下标从 1 开始)
 *
 * 示例：
 *
 *                    1(1~7)
 *                /           \
 *           2(1~4)            3(5~7)
 *         /       \          /      \
 *      4(1~2)   5(3~4)      6(5~6)  7(7)
 *      /  \     /   \       /     \
 *  8(1)  9(2)  10(3) 11(4) 12(5) 13(6)
 */

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 200010

int a[N];
int sum[N << 2]; // 可以通过完全二叉树的节点公式计算得到最多 4 * N 个节点

void pushup(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

// 构建线段树
void build(int l, int r, int rt) {
    if (l == r) {
        sum[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}

// 单点更新
void update(int l, int r, int rt, int pos, int c) {
    if (l == r) {
        sum[rt] = c;
        return;
    }
    int m = (l + r) >> 1;
    if (pos <= m) update(l, m, rt << 1, pos, c);
    else update(m + 1, r, rt << 1 | 1, pos, c);
    pushup(rt);
}

// 区间查询
int query(int l, int r, int rt, int L, int R) {
    if (L == l && r == R) {
        return sum[rt];
    }
    int m = (l + r) >> 1;
    if (R <= m) return query(l, m, rt << 1, L, R);                                   // 完全在左区间：l L R m r
    else if (L > m) return query(m + 1, r, rt << 1 | 1, L, R);                       // 完全在右区间：l m L R r
    else return query(l, m, rt << 1, L, m) + query(m + 1, r, rt << 1 | 1, m + 1, R); // 横跨左右区间：l L m R r
}

int main() {
    int n = 7;
    a[1] = 1;
    a[2] = 2;
    a[3] = 3;
    a[4] = 4;
    a[5] = 5;
    a[6] = 6;
    a[7] = 7;

    build(1, n, 1);
    printf("%d\n", query(1, n, 1, 1, 7));
    printf("%d\n", query(1, n, 1, 1, 4));
    printf("%d\n", query(1, n, 1, 3, 6));
    update(1, n, 1, 1, 0);
    printf("%d\n", query(1, n, 1, 1, 7)); // 0 2 3 4 5 6 7
    update(1, n, 1, 3, 10);
    printf("%d\n", query(1, n, 1, 1, 7)); // 0 2 10 4 5 6 7
    return 0;
}

// 并查集是一种树形的数据结构，可以方便地维护集合的合并和查询问题
// 举例：给出 N 组朋友关系，朋友的朋友即朋友，判断其中 a 和 b 是否是朋友关系

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 5010

// f[x] 表示节点 x 所在集合的根节点
int f[N];

// 初始化并查集
// 初始化时每个集合只有自身一个节点
void init(int n) {
    for (int i = 0; i < n; i++) f[i] = i;
}

// 查询节点 x 所在集合的根节点
// 这里涉及到路径压缩
//
// 假设有如图所示的集合关系，查询节点 6 所在集合根节点时会不断往上直到找到根节点 1，这可能会在集合路径较长时导致查询缓慢
//
//        1
//      / | \
//     2  3  4
//    /
//   5
//  /
// 6
//
// 路径压缩是指在查询根节点时将起所在路径上的节点变为根节点的直接子节点。即：
//
//      1
//  / / | \ \
// 2 3  4 5  6
//
// 当再次查询节点 6/5/2 所在集合根节点时，只用往上查询一层即可得到根节点 1，降低了时间复杂度
//
int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}

// 合并 x 和 y 节点所在的两个集合
void union_2(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) { // 这里选择序号小的节点为合并后的集合根节点，也可以自定义一个估价函数，比如按秩合并
        if (x > y) f[x] = y;
        else f[y] = x;
    }
}

int judge(int x, int y) {
    return find(x) == find(y);
}

int main() {
    init(6);

    union_2(0, 1);
    union_2(2, 3);
    union_2(4, 5);

    printf("%d %d %d\n", judge(0, 1), judge(0, 3), judge(1, 5)); // 1 0 0

    union_2(1, 3);
    union_2(3, 5);

    printf("%d %d %d\n", judge(0, 1), judge(0, 3), judge(1, 5)); // 1 1 1
    return 0;
}

// 未经测试，仅供参考
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 1000010

struct item {
    int id, val;
} q[MAXN], tp;

int main() {
    char op[10];
    int front = 0, rear = 0;
    int in = 0, out = 0; // in, out表示进队、出队编号
    while (scanf("%s", op) && strcmp(op, "END")) {
        if (strcmp(op, "PUSH") == 0) { // 进队，单调递减
            scanf("%d", &tp.val);
            tp.id = in++;
            while (rear > front && tp.val >= q[rear].val) rear--;
            q[rear++] = tp;
        } else if (strcmp(op, "MAX") == 0) { // 查询
            if (front == rear) {
                cout << -1 << endl;
            } else {
                cout << q[front].val << endl;
            }
        } else { // 出队，如果id在当前队首就出队
            if (out == q[front].id) {
                front++;
            }
            out++;
        }
    }
    return 0;
}

// 未经测试，仅供参考
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;

struct item {
    int id, val;
} tp;

// 7 6 10 3 7 4 12 2
int main() {
    int n;
    stack<item> s;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            tp.id = i;
            scanf("%d", &tp.val);
            while (s.size() > 0 && tp.val >= s.top().val) { // 从栈底到栈顶单调递减
                s.pop();
            }
            cout << "left first: " << (s.size() > 0 ? s.top().val : -1) << ", left size: " << s.size() << endl;
            s.push(tp);
        }
    }
    return 0;
}

// 邻接矩阵，遍历时间复杂度：O(N^2)

#include <stdio.h>
#include <string.h>
#define N 110

int n;
int vis[N];
int mpt[N][N];

void init(int nn) {
    n = nn;
    memset(mpt, -1, sizeof(mpt));
    memset(vis, 0, sizeof(vis));
}

void add(int u, int v) {
    mpt[u][v] = 1;
}

void dfs(int u) {
    printf("%d\n", u);
    vis[u] = 1;
    for (int v = 1; v <= n; v++) {
        if (mpt[u][v] && !vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    init(5);
    add(1, 2);
    add(1, 3);
    add(1, 4);
    add(2, 5);
    add(5, 3);
    add(3, 1);
    dfs(1);
    return 0;
}

// 邻接表的数组实现与遍历，遍历时间复杂度：O(E)

#include <stdio.h>
#include <string.h>

#define N 100010
#define M 200010

struct Edge {
    int u, v, w;     // 边的起点、重点、权值
    int next;        // 与节点相连的边的集合中下一条边的序号
};

int tot;             // tot 表示 edge 数组中待分配的边的下标
int head[N];         // head[i] 表示与节点 i 相连的的第一条边的下标
struct Edge edge[M]; // 存储边
int vis[N];

// 初始化
void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
}

// 新建 u->v 的边，边的下标为 tot
// 使用头插法，所以对节点 u 相连的边进行遍历时和添加边时的顺序相反
void add(int u, int v, int w) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;          // 将当前新加的边保存到 head[u]，已有的边接在 edge[head[u]].next
}

// 如果是树的话，使用 pre 记录父节点防止重复遍历
void dfs1(int u, int pre) {
    printf("%d\n", u);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (v != pre) {
            dfs1(v, u);
        }
    }
}

// 如果是图的话(特指带环图)，就必须使用 vis 标记
void dfs2(int u) {
    printf("%d\n", u);
    vis[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (!vis[v]) {
            dfs2(v);
        }
    }
}

int main() {
    init();
    add(1, 2, 1);
    add(1, 3, 1);
    add(1, 4, 1);
    add(2, 5, 1);
    dfs1(1, 1);

    puts("\n");

    init();
    add(1, 2, 1);
    add(1, 3, 1);
    add(1, 4, 1);
    add(2, 5, 1);
    add(5, 3, 1);
    add(3, 1, 1);
    dfs2(1);
    return 0;
}

// 邻接数组写起来稍微有点麻烦
// 很多时候可以直接使用 STL 中的 vector 实现

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define N 100010

int vis[N];
vector<int> vec[N];

void init(int n) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        vec[i].clear();
    }
}

// 添加双向边
void add(int u, int v) {
    vec[u].push_back(v);
    vec[v].push_back(u);
}

// 遍历
void dfs(int u) {
    printf("%d\n", u);
    vis[u] = 1;
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    init(5);
    add(1, 2);
    add(1, 3);
    add(1, 4);
    add(2, 5);
    add(5, 3);
    add(3, 1);
    dfs(1);
    return 0;
}

/*
 * 树的直径：树中相距最远的两个节点之间的距离
 *
 * 方法1：树上 DP
 * 方法2：从树上任意一节点出发 dfs/bfs 找到最远的节点 u，再从节点 u 出发找到最远的节点 v，路径 uv 即为树的直径
 *       证明：https://www.luogu.com.cn/blog/Loveti/problem-tree
 */

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 100

int n, m;
int dp[MAX][2]; // dp[u][0/1] 分别表示以节点 u 为根节点的最长、次长路径长度
vector<int> edges[MAX];

void dfs1(int u, int pre) {
    dp[u][0] = dp[u][1] = 0;
    for (int i = 0; i < edges[u].size(); i++) {
        int v = edges[u][i];
        if (v != pre) {
            dfs1(v, u);
            if (dp[v][0] + 1 >= dp[u][0]) { // 儿子最长 + 1 >= 当前最长，更新最长和次长
                dp[u][1] = dp[u][0];
                dp[u][0] = dp[v][0] + 1;
            } else if (dp[v][0] + 1 > dp[u][1]) {
                dp[u][1] = dp[v][0] + 1;
            }
        }
    }
}

int solve1() {
    dfs1(1, 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i][0] + dp[i][1]);
    }
    return ans;
}

int pos; // 最远的节点下标、距离
int dis;

void dfs2(int u, int pre, int d) {
    if (d > dis) {
        pos = u;
        dis = d;
    }
    for (int i = 0; i < edges[u].size(); i++) {
        int v = edges[u][i];
        if (v != pre) {
            dfs2(v, u, d + 1);
        }
    }
}

int solve2() {
    dis = 0;
    dfs2(1, 1, 0);

    dis = 0;
    dfs2(pos, pos, 0);
    return dis;
}

/*
ans=5
9 8
1 2
1 3
1 4
2 5
2 6
6 7
6 8
4 9
*/
int main() {
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    cout << solve1() << " " << solve2() << endl;
    return 0;
}