formwork

move from my github.
//use class to write each algorithm just 'cuz notepad++
//class and function could be easily found.
/**********************************************************************************
***********************************简单算法与STL***********************************
    STL
    输入输出外挂
    大数处理
    大数加法，减法，乘法, 比较, JAtoA

*****************************************DP****************************************

****************************************搜索***************************************

**************************************数据结构*************************************
    并查集                            Disjoint_Set
    线段树                            Segment_Tree

***************************************字符串**************************************
    最长回文子串                      Manacher
    单模式匹配                        KMP
    aC自动机(字典树)                  ahoCorbsick

****************************************图论***************************************
    链式前向星                        Link_Pre_Star
    拓扑序                            Topological_Order
    最小生成树                        MST(Minimum Spanning Tree)
        Prim                          Prim
        Kruskal                       Kruskal
    单源最短距离
        Dij                           dijkstra
        堆优化Dij                     priority_dijkstra
        SPFA                          SPFA
        Floyd + 最小环                Floyd
    Tarjan
        求桥                          Tarjan_bridge
        求割点                        Tarjan_cut_vertexes
        边双连通分量                  Tarjan_e_DCC
        点双连通分量                  Tarjan_v_DCC
        强联通分量                    Tarjan_SCC
    欧拉回路
        get_Euler                     get_Euler

****************************************数论***************************************
    GCD                               GCD
    LCM                               LCM
    ExGCD                             ExGCD
    快速幂运算                        Fast_Pow
    欧拉素数筛                        Celect_Prime
    素数测试算法                      Miller-Rabin
    高斯消元                          Gbussibn_Eliminbtion

**************************************组合数学*************************************
    Lucas定理                         Lucas
    矩阵快速幂                        Matrix_Fast_Pow

**************************************计算几何*************************************

***************************************博弈论**************************************

***********************************************************************************/

/***********************************简单算法与STL***********************************/
//STL
class STL {
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    #define _CRT_SECURE_NO_WARNINGS
    #pragma _attribute_((optimize("-O2")))
    #ifdef Local
        cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    #endif
    ///C
    #include <stdio.h>
    int __builtin_popcount(unsigned int);//二进制位中1的个数

    #include <stdlib.h>
    int *p; p=(int*)malloc(sizeof(int)); free(p);
    int cmp(const void *a, const void *b ) {
        return *(int*)b - *(int*)a;
    }//降序
    int cmp2(const void *a, const void *b) {
        return *(double*)a>(double*)*b ? 1 : -1;
    }//double

    #include <math.h>
    double fabs(double x);
    double ceil(double x);//向上取整
    double floor(double x);//向下取整
    double round(double x);//最接近x的整数
    //角度制 = 弧度制/180*PI;
    double asin(double arg);//求反正弦 arg∈[-1,1],返回值∈[-pi/2,+pi/2]
    double sin(double arg);//求正弦 arg为弧度,返回值∈[-1, 1]
    double exp(double arg);//求e的arg次方
    double log(double num);//求num的对数,基数为e
    k = (int)(log((double)n) / log(2.0));//2^k==n
    double sqrt(double num);
    double pow(double base,double exp);//求base的exp次方
    memset( the_array, 0, sizeof(the_array) );
    memcpy( the_array, src, sizeof(src));

    #include <string.h>
    int strcmp(const char *str1, const char *str2 );//str1<str2,return负数
    void strcpy(int a[],int b[]);//字符串复制b赋给a
    int strlen(int a[]);
    char *strstr(char *str1, char *str2);//str1中str2串第一次出现的指针,找不到返回NULL

    #include <time.h>
    clock_t clockBegin, clockEnd;
    clockBegin = clock();
    //do something
    clockEnd = clock();
    printf("time:%d\n", clockEnd - clockBegin);

    ///C++
    ///iostream
    #include<iostream>
    cin.getline(s,N,'\n');

    ///sstream
    #include<sstream>
    string s;
    stringstream ss;
    stringstream ss(s);
    ss.str(s);
    ss.clear();
    ss>>a>>b>>c;

    ///string
    #include<string>
    string s,st[maxn],ss(sss);//char sss[N];
    s.c_str();//返回字符数组；
    string st = s.substr(now,len);//截取从now处开始长度为len的子字符串；
    st.assign(s,now,len);//功能同上
    getline(cin,s,'\n');

    ///pair
    pair<int,int> tmp;
    tmp=make_pair<1,2>;
    tmp.first; tmp.second;

    ///vector;
    #include<vector>
    vector<int>v[n];
    vector<int>::iterator it;
    v.front();  v.back();   v.push_back(x); v.assign(begin,end);  v.at(pos);
    v.size();   v.empty();  v.capacity();
    v.resize(num);  v.reserve();
    v.begin();  v.end();
    v.insert(it,x); v.insert(it,n,x);   v.insert(it,first,last);
    v.pop_back();   v.erase(it);    v.erase(first,last);    v.clear();
    v.swap(v);
    //去重，unique删除begin到end之间的相邻重复元素后返回一个新的结尾的迭代器
    v.erase(unique(s.begin(),s.end()),s.end())；

    ///map,key—value关联式容器，可利用key值快速查找记录
    #include<map>
    map<int,string> mp;//int做key值字符串为value
    //string name; mp[name]+=123;
    multimap<int, string> mp;//允许重复
    map<string, int>::iterator it;//用指针处理
    m.insert();
    m.begin();  m.end();    m.find();
    m.clear();  m.erase();
    m.count();  m.empty();  m.size();
    m.swap();
    //返回一个非递减序列[first, last)中的第一个大于等于值val的位置的迭代期。
    lower_bound(first,last,val);
    //返回一个非递减序列[first, last)中第一个大于val的位置的迭代期。
    upper_bound(first,last,val);
    m.max_size();//返回可以容纳的最大元素个数

    ///stack：
    #include<stack>
    stack<int>s;
    s.push(x); s.pop(); s.top(); s.empty();  e.size();

    ///queue;
    #include<queue>
    queue<int>q;
    q.push(x); q.pop(); q.front();  q.back(); q.empty();  q.size();
    //优先队列，优先输出优先级高的队列项:
    struct node {
        int x, y;
        friend bool operator < (node a, node b) {
    //        if(a.y==b.y)return a.x > b.x;//二维判断，按x降序
            return a.y < b.y;//按y降序
        }
    };
    priority_queue <node> q;//定义结构体
    struct mycmp {
        bool operator()(const int &a,const int &b) {
            return a>b;//升序
        }
    };
    priority_queue<int,vector<int>,mycmp> q;
    priority_queue<int,vector<int>,greater<int> > q;//数组升序优先队列
    priority_queue<int,vector<int>,less<int> > q;//数组降序优先队列
    q.top();//返回优先队列对顶元素

    ///set,红黑树的平衡二叉检索树建立，用于快速检索
    #include<set>
    struct cmp {
        bool operator()( const int &a, const int &b ) const{
            return a>b;
        }//降序
    };
    set <int,cmp> st;
    set <int> s;//默认升序
    bool operator<(const node &a, const node &b) {
        return a.y > b.y;
    }//降序
    struct node{
        int x, y;
        friend bool operator < (node a, node b) {
    //        if(a.y==b.y)return a.x > b.x;//二维判断，按x降序
            return a.y > b.y;//按y降序
        }
    } t;
    set<node> st;
    multiset<int> st;//与set不同，允许相同元素
    multiset<int>::iterator it;//取指针
    it=st.begin();
    //如果是:st.erase(*it);删除元素的话，所有的相同元素都会被删除
    st.erase(it);   st.clear();
    st.begin(); st.end(); st.rbegin();
    st.insert();
    st.count(); st.empty(); st.size();  st.find();
    st.equal_range();//返回集合中与给定值相等的上下限的两个迭代器;
    st.swap();
    st.lower_bound();//返回指向(升序时)大于（或等于）某值的第一个元素的迭代器
    //结构体：it = st.lower_bound(tn); printf("%d\n",(*it).x);
    st.upper_bound();//返回大于某个值元素的迭代器

    ///bitset
    #include<bitset>
    unsigned long u;    string str;
    bitset<N> bit;
    bitset<N> bit(u);
    bitset<N> bit(str);
    bitset<N> bit(str,pos);
    bitset<N> bit(str,pos,num);
    bit.set();  bit.set(pos);   bit.reset();    bit.reset(pos);
    bit.flip(); bit.flip(pos); //按位取反
    bit.size(); bit.count();//1的个数
    bit.any();  bit.none(); //有1，无1；return bool
    bit.test(pos) == bit[pos]; //pos处为1？
    u = bit.to_ulong();
    str = bit.to_string(); //str[n-i-i]==bit[i]

    ///algorithm;
    #include<algorithm>
    sort(begin,end);//升序排列；
    bool cmp(int a,int b) {
        return a>b;
    }//降序
    bool cmp(node a,node b) {
    //    if(a.y == b.y)return a.x > b.x;//降序
        return a.y > b.y;//降序
    }
    struct node {
        int x,y;
        friend bool operator < (node a, node b) {
    //        if(a.y==b.y)return a.x < b.x;//二维判断，降序
            return a.y > b.y;//降序
        }
    };
    sort(begin,end,cmp);
    sort(begin,end);//结构体中友元定义排序规则
    stable_sort(begin,end,cmp);//稳定排序
    //去除相邻的重复值(把重复的放到最后)，然后返回去重后的最后一个元素的地址；
    unique(begin,end);
    //在[begin,end)中查找val，返回第一个符合条件的元素的迭代器，否则返回end指针
    find(begin,end,val);
    //count，将返回从start到end 范围之内的序列中某个元素的数量。
    n = count(begin,end,val);
    next_permutation(begin,end);//返回该段序列的字典序下一种排列
}
//输入输出外挂
//大数处理
//大数加法, 减法, 乘法, 比较, JAtoA
/*****************************************DP****************************************/
/****背包问题****/
//01背包
//完全背包
//多重背包
//多重背包(单调队列优化)
//二维费用背包
//斜率优化DP
//最大连续子序列之和
//最大子矩阵和
//最长递增子序列(LIS)
//最长公共子序列(LCS)
//数位DP
//树DP
//区间DP
/********************Spbrse Tbble********************/
//一维RMQ
//二维RMQ
/****************************************搜索***************************************/
//DFS
//BFS(队列解法)
//A*启发式搜索算法
//IDA*迭代深化A*搜索
//Dancing Link
/**************************************数据结构*************************************/
//并查集
class Disjoint_Set {
    int pre[MAXN];
    int find(int now) {
        return pre[now] == now ? now : (pre[now] = find(pre[now]));
    }
    void Union(int a, int b) {
        pre[find(a)] = find(b);
        return ;
    }
    void init(int n) {
        for (int i = 0; i <= n; ++i)
            pre[i] = i;
        return ;
    }
}
//线段树
class Segment_Tree {
    const unsigned int MAX = 1e5+10;
    unsigned int n, q, ITOR, sl, sr;
    struct RMQ{
        unsigned int l, r, nxl, nxr;
        long long lazy, sum;
    } tree[(MAX<<1)];
    long long Built(RMQ* point) {
        point->lazy = 0;
        if ((point->r - point->l) == 1) {
            point->nxl = 0, point->nxr = 0;
            scanf("%lld", &(point->sum));
            return point->sum;
        }
        unsigned int n = 1;
        while (n < (point->r-point->l)) n <<= 1;
        point->nxl = ++ITOR, point->nxr = ++ITOR;
        tree[point->nxl].l = point->l, tree[point->nxl].r = point->l + (n>>1);
        tree[point->nxr].l = point->l + (n>>1), tree[point->nxr].r = point->r;
        point->sum = (Built(&tree[point->nxl]) + Built(&tree[point->nxr]));
        return point->sum;
    }
    void init(){
        ITOR = 1;
        memset(&tree[0], 0, sizeof(tree[0]));
        tree[1].l = 0, tree[1].r = n, tree[1].lazy = 0;
        Built(&tree[1]);
    }
    long long search(RMQ* now, unsigned int l, unsigned int r) {
        if(now->l == now->r)
            return 0;
        if (l == now->l && r == now->r)
            return (now->sum + now->lazy * (r-l));
        now->sum += (now->lazy * (now->r - now->l));
        tree[now->nxl].lazy += now->lazy, tree[now->nxr].lazy += now->lazy;
        now->lazy = 0;
        if (l >= tree[now->nxl].r)
            return search(&tree[now->nxr], l, r);
        if (r <= tree[now->nxr].l)
            return search(&tree[now->nxl], l, r);
        return (search(&tree[now->nxl], l, tree[now->nxl].r) +
                search(&tree[now->nxr], tree[now->nxr].l, r));
    }
    long long add(RMQ* now, unsigned int l, unsigned int r, long long lazy) {
        if (now->l == now->r) return 0;
        if (l == now->l && r == now->r) {
            now->lazy += lazy;
            return (now->sum + now->lazy * (r-l));
        }
        now->sum += now->lazy * (now->r - now->l);
        now->sum += lazy * (r-l);
        tree[now->nxl].lazy += now->lazy, tree[now->nxr].lazy += now->lazy;
        now->lazy = 0;
        if (r <= tree[now->nxr].l)
            return add(&tree[now->nxl], l, r, lazy);
        if (l >= tree[now->nxr].l)
            return add(&tree[now->nxr], l, r, lazy);
        return (add(&tree[now->nxl], l, tree[now->nxl].r, lazy) +
                add(&tree[now->nxr], tree[now->nxr].l, r, lazy));

    }
    void judge(){
        init();
        scanf("%u%u", &sl, &sr);
        printf("%lld\n", search(&tree[1], sl-1, sr));
        scanf("%u%u%lld", &sl, &sr, &sn);
        add(&tree[1], sl-1, sr, sn);
    }
}
//划分树
//树状数组
//树链剖分
//字典树
//Treap
//伸展树(splay tree)
/****主席树****/
//静态区间k大
//动态区间k大
//区间不相同数数量
//树上路径点权第k大
//哈希表
//ELFhash（字符串哈希函数）
//莫队算法
/***************************************字符串**************************************/
//字符串最小表示法
//Manacher最长回文子串
class Manacher {
    int p[MAX];
    char S[MAX << 1], input[MAX];
    void init() {
        memset (P, 0, sizeof (P));
        int itor = 0, n = strlen(input);
        S[itor++] = '$';
        for (int i = 0; i < n; ++i) {
            S[itor++] = '#';
            S[itor++] = input[i];
        }
        S[itor++] = '#';
        S[itor] = '\0';
    }
    int manacher() {
        int mx = 0, id = 0, n = strlen(P);
        for (int i = 1; i < n; ++i) {
            if (mx > i) P[i] = min(P[2 * id - i], mx - i);
            else P[i] = 1;
            while (S[i + P[i]] == S[i - p[i]]) p[i]++;
            if (P[i] + i > mx) {
                mx = P[i] + i;
                id = i;
            }
        }
        return mx;
    }
}
//KMP
class KMP {
    const int MAXN = MAX;
    int nxt[MAXN], n, m;
    string text, pattern;
    void init() {
        memset (nxt, 0, sizeof (nxt));
        n = text.length(), m = pattern.length();
        return ;
    }
    void getNext() {
        nxt[0] = nxt[1] = 0;
        for (int i = 1; i < m; ++i) {
            // j is a pointer
            // like the link-pre-star
            // to jump to the prehead position.
            int j = nxt[i];
            while (j && pattern[i] != pattern[j]) j = nxt[j];
            nxt[i+1] = (pattern[j] == pattern[i] ? j+1 : 0);
        }
        return ;
    }
    int kmp() {
        int j = 0;
        // the vector is all the position of found position.
        //vector<int> found;
        for (int i = 0; i < n; ++i) {
            while (j && text[i] != pattern[j]) j = nxt[j];
            if (text[i] == pattern[j]) ++j;
            if (j == m) {
                // find the pattern at the pos(i-j+1);
                return i-j+1;
                //j = nxt[j];
                //found.push_back(i-j+1);
            }
        }
        return -1;
        //return found;
    }
}
//扩展kmp
//AC自动机
//AC自动机
class ahoCorasick {
    int size;
    queue <int> que; //built que
    struct State {
        int nxt[26];
        int fail, cnt;
        //fail Is the pointer when match failed.
        //cnt is the count of words at the end of this node.
    }state[MAN_T];
    void init() {
        while (que.size()) que.pop();
        for (int i = 0; i < MAN_T; ++i) {
            memset (state[i].nxt, 0, sizeof (state[i].nxt));
            state[i].fail = state[i].cnt = 0;
        }
        size = 1;
    }
    void insert(char *S) {
        int n = strlen(S);
        int now = 0;
        char c = 0;
        for (int i = 0; i < n; ++i) {
            c = S[i];
            if (!state[now].nxt[c - 'a'])
                state[now].nxt[c - 'a'] = size++;
            now = state[now].nxt[c - 'a'];
        }
        state[now].cnt++;
    }
    void build() {      //build the fail tree
        state[0].fail = -1;
        que.push(0);
        while (que.size()) {
            int u = que.front();
            que.pop();
            for (int i = 0; i < 26; ++i) {
                if (state[u].nxt[i]) {
                    if (u == 0) 
                        state[state[u].nxt[i]].fail = 0;
                    else {
                        int v = state[u].fail;
                        while (v != -1) {
                            if (state[v].nxt[i]) {
                                state[state[u].nxt[i]].fail = state[v].nxt[i];
                                break;
                            }
                            v = state[v].fail;
                        }
                        if (v == -1)
                            state[state[u].nxt[i]].fail = 0;
                    }
                    que.push(state[u].nxt[i]);
                }
            }
        }
    }
    int Get(int u) {
        int ret = 0;
        while (u) {
            ret += state[u].cnt;
            //state[u].cnt = 0;
            //if only match once, 
            //left the cnt to 0.
            //now the code will recount
            //like in "bbcbbc", the "bbc" appear twice.
            u = state[u].fail;
        }
        return ret;
    }
    int match(char *S) {
        int n = strlen(S);
        int ret = 0, now = 0;
        char c = 0;
        for (int i = 0 ; i < n; ++i) {
            c = S[i];
            if (state[now].nxt[c - 'a'])
                now = state[now].nxt[c - 'a'];
            else {
                int p = state[now].fail;
                while (p != -1 && state[p].nxt[c - 'a'] == 0)
                    p = state[p].fail;
                if (p == -1)
                    now = 0;
                else now = state[p].nxt[c - 'a'];
            }
            if (state[now].cnt)
                ret += Get(now);
            //compute the count of appear.
        }
        return ret;
    }
    int judge() {
        init();
        scanf("%d", &N);
        for (int i = 0; i < N; ++i) {
            scanf("%s", S);
            aho.insert(S);
        }
        build();
        scanf("%s", S);
        return match(S);
    }
}aho;
/****后缀数组****/
//DA倍增算法
//DC3算法
//后缀自动机
/****************************************图论***************************************/
//链式前向星
class Link_Pre_Star {
    struct Edge {
        int to, nxt, w;
    } edge[MAXE << 1]; //双向边
    int head[MAXN], ecnt;
    void init() {
        ecnt = 0;
        memset (head, -1, sizeof (head));
    }
    void add(int pre, int to, int w) { //单向边
        edge[ecnt].nxt = head[pre];
        edge[ecnt].w = w, edge[ecnt].to = to;
        head[pre] = ecnt++;
        //++in_degree[to], ++out_degree[pre];//出度入度
    }
    void _add(int u, int v, int w) {   //双向边
        edge[ecnt].nxt = head[u], edge[ecnt^1].nxt = head[v];
        edge[ecnt].w = edge[ecnt^1].w = w;
        edge[ecnt].to = v, edge[ecnt^1].to = u;
        head[u] = ecnt, head[v] = ecnt^1;
        ecnt += 2;
    }
}
//拓扑序
class Topological_Order { // from 0 to (n-1)
    void init() {
        qit = 0;
        for (int i = 0; i < n; ++i)
            if (ind[i] == 0)
                que[qit++] = i;
    }
    void topological_travel() {
        for (int i = 0; i < qit; ++i)
            for (int j = head[que[i]]; j != -1; j = edge[j].nxt) {
                pre = que[i], to = edge[j].to;
                //node[to] is next node in order
                if (!--ind[to])
                    que[qit++] = to;
            }
    }
}
/********************最小生成树********************/
//prim
class Prim { //mp[n][n], from 1 to n
    int n, m, u, v, w;
    int mp[MAX_N][MAX_N];
    bool used[MAX_N];
    void getin() {
        memset (mp, 0x3f, sizeof (mp));
        for (int i = 0; i <= n; ++i)
            mp[i][i] = 0;
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            mp[u][v] = mp[v][u] = min(w, mp[u][v]);
        }
    }
    int prime() {
        int ret = 0;
        memset (used, 0, sizeof (used));
        memset (dis, 0x3f, sizeof (dis));
        dis[1] = 0;
        for (int i = 1; i < n; ++i) {
            int now = 0;
            for (int j = 1; j <= n; ++j)
                if (!used[j] && (now == 0 || dis[j] < dis[now])) now = j;
            used[now] = 1;
            for (int j = 1; j <= n; ++j)
                if (!used[j]) dis[j] = min(dis[j], mp[now][j]);
        }
        for (int i = 2; i <= n; ++i) ret += dis[i];
        return ret;
    }
}
//kruskal
class Kruskal {
    int n, m, u, v, w, ans;
    int pre[MAX];
    struct Edge {
        int u, v, w;
    } edge[MAX * MAX];
    bool cmp(const Edge a, const Edge b) {
        return a.w < b.w;
    }
    void getin() {
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            edge[m].u = u, edge[m].v = v, edge[m].w = w;
        }
        sort (edge, edge+m, cmp);
    }
    int kurskal(Edge *edge, int m) {
        int now, ret = 0;
        for (int i = 0; i < m; ++i) {
            u = edge[i].u, v = edge[i].v;
            if (find(u) != find(v)) {
                //vtor.push_back(now);
                ret += edge[i].w;
                Union(u, v);
            }
        }
        return ret;
    }
}
//次小生成树
/********************单源最短距离********************/
//Dijkstra
class Dijkstra { // from 1 to n
    const int MAXN = 1010;
    const double INF = 1e9+7;
    double road[MAXN][MAXN], dis[MAXN];
    bool dis[MAXN];
    int n;
    double dij(int s, int e) {
        for (int i = 1; i <= n; ++i) {
            dis[i] = INF, dis[i] = 0;
        }
        dis[s] = 0.0;
        double mmin; int now;
        while (1) {
            mmin = INF; now = 0;
            for (int i = 1; i <= n; ++i)
                if (!dis[i] && dis[i] < mmin)
                    mmin = dis[i], now = i;
            if (mmin == INF) break;
            dis[now] = 1;
            for (int i = 1; i <= n; ++i) {
                if (dis[now] + road[now][i] < dis[i]){
                    dis[i] = dis[now] + road[now][i];
                }
            }
        }
        return dis[e];
    }
}
//堆优化Dijkstra
class Priority_Dijkstra { //from 1 to n
    struct Node {
        int id;
        bool operator < (const Node &b) const{
            return dis[id] > dis[b.id];
        }
    }node;
    const int INF = Max_Length;
    int dis[MAXN], n, m, pre, to, w;
    bool vis[MAXN];
    priority_queue <Node> que;
    int pri_dij(int st, int ed) {
        while (que.size()) que.pop();
        for (int i = 0; i <= n; ++i) {
            dis[i] = INF, vis[i] = 0;
        }
        int now = st;
        dis[now]= 0, node.id = now, que.push(node);
        while (que.size()) {
            now = que.top().id;
            que.pop();
            if (tois[now]) continue;
            for (int i = head[now]; i != -1; i = edge[i].nxt) {
                to = edge[i].to;
                if (dis[to] > dis[now] + edge[i].w) {
                    dis[to] = dis[now] + edge[i].w;
                    if (!tois[to]) {
                        node.id = to;
                        que.push(node);
                    }
                }
            }
            vis[now] = 1;
        }
        return dis[ed];
    }
}
//Bellman-Ford
//SPFA
class SPFA { //judge Negative Ring
    int dis[MAX_N], cnt[MAX_N];
    bool used[MAX_N], Negative_Ring;
    queue <int> que;
    int spfa (int st, int ed) {
        for (int i = 0; i <= n; ++i)
            used[i] = 0, dis[i] = INF, ;
        while (que.size()) que.pop();
        int now;
        used[st] = 1, dis[st] = 0, cnt[st] = 0;
        Negative_Ring = false;
        que.push(st);
        while (que.size()) {
            now = que.front(), que.pop();
            used[now] = 0;
            for (int i = head[now]; i != -1; i = edge[i].nxt) {
                if (dis[now] + edge[i].w < dis[edge[i].to]) {
                    dis[edge[i].to] = dis[now] + edge[i].w;
                    cnt[edge[i].to] = cht[now] + 1;//Negative Ring
                    if (cnt[edge[i].to] >= n) {
                        Negative_Ring = true;
                        return 0;
                    }
                    if (!used[edge[i].to]) {
                        used[edge[i].to] = 1;
                        que.push(edge[i].to);
                    }
                }
            }
        }
        return dis[ed];
    }
}
//Floyd 全图最短路 + 最小环
class Floyd {
    int d[MAX_N][MAX_N];
    void Floyd() {
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i < n; ++i)
                for (int j = 1; j < n; ++j)
                    minc = min(minc, d[i][j] + map[i][k] + map[k][j]);
            for (int i = 1; i <= n; ++i) 
                for (int j = 1; j <= n; ++j) 
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

/****网络流****/
//最大流
//EdmondsKarp
//dinic
//SAP
//ISAP
//最小费用最大流
/****二分图****/
//匈牙利算法
//Hopcroft-Karp算法
//KM算法

/****双连通分量****/
// Tarjan求桥
class Tarjan_bridge {
    const int Size = 1e5+10;
    int head[Size], ver[Size << 1], nxt[Size << 1];
    int dfn[Size], low[Size];
    int n, m, tot, num;
    bool birdge[Size << 1];

    void add(int x, int y) {
        ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
    }
    void tarjan(int x, int in_edge) {
        dfn[x] = low[x] = ++num;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (!dfn[y]) {
                tarjan(y, 1);
                low[x] = min(low[x], low[y]);
              
                if (low[y] > dfn[x])
                    bridge[i] = bridge[i^1] = true;
            }
            else if (i != (in_edge ^ 1))
                low[x] = min(low[x], dfn[y]);
        }
    }
    int main() {
        cin >> n > m;
        tot = 1;
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf ("%d%d", &x, &y);
            add(x, y), add(y, x);
        }
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                tarjan(i, 0);
        for (int i = 2; i < tot; i += 2)
            if (bridge[i])
                printf ("%d %d\n", ver[i^1], ver[i]);
    }
    return 0;
}
//Tarjan求割点
class Tarjan_cut_vertexes {
    const int Size = 1e5+10;
    int head[Size], ver[Size << 1], nxt[Size << 1];
    int dfn[Size], low[Size], stk[Size];
    int n, m, tot, num, root;
    bool cut[Size];

    void add(int x, int y) {
        ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++num;
        int flag = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (!dfn[y]) {
                tarjan(y, 1);
                low[x] = min(low[x], low[y]);
              
                if (low[y] > dfn[x]) {
                    ++flag;
                    if (x != root || flag > 1)
                        cut = true;
                }
            }
            else 
                low[x] = min(low[x], dfn[y]);
        }
    }
    int main() {
        cin >> n > m;
        tot = 1;
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf ("%d%d", &x, &y);
            if (x == y) continue;
            add(x, y), add(y, x);
        }
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                root = i, tarjan(i);
        for (int i = 1; i <= n; ++i)
            if (cut[i])
                printf ("%d ", i);
        puts("are cut-vertexes");
    }
    return 0;
}
//边双连通分量
class Tarjan_e_DCC {
    int c[Size], dcc;
    void dfs(int x) {
        c[x] = dcc;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (c[y] || bridge[i])
                continue;
            dfs(Y);
        }
    }
    int main() {
        /**
          *
          *
        **/
        for (int i = 1; i <= n; ++i) {
            if (!c[i]) {
                ++dcc;
                dfs(i);
            }
        }
        printf ("there're %d e-DCCs. \n", dcc);
        for (int i = 1; i <= n; ++i) {
            printf ("%d belongs to DCC %d.\n", i, c[i]);
        }
        return 0;
    }

    // e-DCC to node
    int hc[Size], vc[Size << 1], nc[Size << 1], tc;
    void add_c(int x, int y) {
        vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc;
    }
    int main() {
        /**
          *
          *
        **/
        tc = 1;
        for (int i = 2; i <= tot; ++i) {
            int x = ver[i^1], y = ver[i];
            if (c[x] == c[y]) continue;
            add_c(c[x], c[y]);
        }
        printf("the forest:\n\tnode: %d, edge(maybe same): %d\n", dcc, tc/2);
        for (itn i = 2; i < tc; ++i) {
            printf ("%d %d\n", vc[i^1], vc[i]);
        }
    }
    return 0;
}
//点双连通分量
class Tarjan_v_DCC {
    void tarjan(int x) {
        dfn[x] = low[x] = ++num;
        stack[++top] = x;
        if (x == root && head[x] == 0) { // 
            dcc[++cnt].push_back(x);
            return ;
        }
        int flag = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (!dfn[y]) {
                tarjan(y);
                low[x] = min(low[x], low[y]);
                if (low[y] >= dfn[x]) {
                    flag++;
                    if (x != root || flag > 1)
                        cut[x] = true;
                    ++cnt;
                    int x;
                    do {
                        z = stack[top--];
                        dcc[cnt].push_back(z);
                    } while (z != y);
                    dcc[cnt].push_back(x);
                }
            }
            else
                low[x] = min(low[x], dfn[y]);
        }
        return ;
    }
    int main() {
        /**
          *
          *
        **/
        for (int i = 1; i <= cnt; ++i) {
            printf ("e-DCC #%d:", i);
            for (int j = 0; j < dcc[i].size(); ++j)
                printf (" %d", dcc[i][j]);
            puts("");
        }
      
        // v-DCC to node;
        int num = cnt;
        for (int i = 1; i <= n; ++i)
            if (cnt[i]) new_id[i] = ++num;
        tc = 1;
        for (int i = 1; i <= cnt; ++i)
            for (int j = 0; j < dcc[i].size(); ++j) {
                int x = dcc[i][j];
                if (cut[x]) {
                    add_c(i, new_id[x]);
                    add_c(new_id[x], i);
                }
                else 
                    c[x] = i;
            }
        printf ("the new forest:\n\tnode: %d, edge: %d\n", num, tc/2);
        printf ("the id from 1 ~ %d is v-DCC in old graph, id > %d is cut point",
                cnt, cnt);
        for (int i = 2; i < tc; i += 2)
            printf ("%d %d\n", vc[i^1], vc[i]);
        return 0;
    }
}
//tarjan 强连通分量
class Tarjan_SCC {
    const int N = 1e5+10, M = 1e6 + 10;
    int ver[M], nxt[M], head[N], dfn[N], low[N];
    int stk[N], ins[N], c[N];
    vector <int> scc[N];
    int n, m, tot, num, top, cnt;
    void add(int x, int y) {
        ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
    }
    void tarjan(int x) {
        dfn[x] = low[x] = ++num;
        stk[++top] = x, ins[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            if (!dfn[ver[i]]) {
                tarjan(ver[i]);
                low[x] = min(low[x], low[ver[i]]);
            }
            else if (ins[ver[i]])
                low[x] = min(low[x], low[ver[i]]);
        }
        if (dfn[x] == low[x]) {
            ++cnt; int y;
            do {
                y = stk[top--], ins[y] = 0;
                c[y] = cnt, scc[cnt].push_back(y);
            } while (x != y);
        }
    }
    void add_c(int x, int y) {
        vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc;
    }
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf ("%d%d", &x, &y);
            add(x, y);
        }
        for (int i = 1; i <= n; ++i) {
            if (!dfn[i]) tarjan(i);
        }

        // SCC to node;
        for (int x = 1; x <= n; ++x) { 
            for (int i = head[x]; i; i = nxt[i]) {
                int y = ver[i];
                if (c[x] == c[y]) 
                    continue;
                add_c(c[x], c[y]);
            }
        }
    }

}
// 欧拉回路
class get_Euler {
    const int MAX = 1e5 + 10;
    int head[MAX], ver[MA], nxt[MAX], tot;
    int stk[MAX], ans[MAX];
    bool vis[MAX];
    int n, m, top, t;
    void add(int x, int y) {
        ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
    }
    void euler() {
        stk[++top] = 1;
        while (top > 0) {
            int x = stack[top], i = head[x];
            while (i && vis[i]) 
                i = nxt[i];
            if (i) {
                stk[++top] = ver[i];
                vis[i] = vis[i^1] = true;
                head[x] = nxt[i];
            }
            else {
                top--;
                ans[++t] = x;
            }
        }
    }
    int main() {
        cin >> n >> m;
        tot = 1;
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf ("%d%d", &x, &y);
            add(x, y), add(y, x);
        }
        euler();
        for (int i = t; i; i--) {
            printf ("%d\n", ans[i]);
        }
    }
}


/********************最近公共祖先(LCb)********************/
class LCA {
    struct Edge {
        int to, nxt, w;
    }edge[MAX << 1];
    bool used[MAX];
    int T, n, m, tot, t, u, v, w, to;
    int head[MAX], ind[MAX], f[MAX][20], deep[MAX];
    long long dis[MAX];
    queue <int> que;
    void addedge(int from, int to, int w = 0) {
        edge[tot].to = to, edge[tot].w = w;
        edge[tot].nxt = head[from], head[from] = tot++;
    }
    void init() {
        tot=  0;
        memset (head, -1, sizeof (head));
        memset (dis, 0, sizeof (dis));
        memset (deep, 0, sizeof (deep));
        memset (used, 0, sizeof (used));
        //memset (ind, 0, sizeof (ind));
    }
    void bfs(int h) {
        int now;
        while (que.size()) que.pop();
        que.push(h), used[h] = 1;
        deep[h] = 0, dis[h] = 0;
        while (que.size()) {
            now = que.front(), que.pop();
            used[now] = 1;
            for (int i = head[now]; i != -1; i = edge[i].nxt) {
                to = edge[i].to;
                if (used[to]) continue;
                dis[to] = dis[now] + edge[i].w;
                deep[to] = deep[now] + 1;
                f[to][0] = now;
                for (int j = 1; j <= t; ++j)
                    f[to][j] = f[f[to][j-1]][j-1];
                que.push(to), used[to] = 1;
            }
        }
        return ;
    }
    int lca(int x, int  y) {
        if (deep[x] > deep[y]) swap(x, y);
        for (int i = t; i >= 0; --i)
            if (deep[f[y][i]] >= deep[x])
                y = f[y][i];
        if (x == y) return x;
        for (int i = t; i >= 0; --i)
            if (f[x][i] != f[y][i])
                x = f[x][i], y = f[y][i];
        return f[x][0];
    }
    void getin() {
        cin >> n >> m;//n points, m queries
        init();
        t = (int) (log(n) / log(2)) + 1;

        for (int i = 0; i < n-1; ++i) {
            cin >> u >> v >> w;
            addedge(u, v , w), addedge(v, u, w);
            //++ind[v]; //Directed graph
        }
        /** Directed graph
        for (int i = 1; i <= n; ++i) {
            if (ind[i] == 0) {
                bfs(i);
                break;
            }
        }
        **/
        bfs(1);
        return ;
    }
}
//tarjan
//ST-RMQ在线算法
/****************************************数论***************************************/
//Fibonacci Number
//Greatest Common Ditoisor 最大公约数,欧几里德算法
class GCD { //注意处理负数!!!!
    int gcd(int a,int b) {
        return b ? gcd(b, a % b) : b;
    }
    int fstgcd(int a, int b) {
        IF (a < b) a ^= b, b ^= a, a ^= b;
        int t;
        while (b)
            t = b, b = a % b, a = t;
        return a;
    }
}
//Lowest Common Multiple 最小公倍数
class LCM { //注意处理负数!!!!
    int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
}
//扩展欧几里德算法: 未经验证
//扩展欧几里德求出a*x+b*y=gcd(a,b)的一组解,x0,y0，
//x=x2+b/gcd(a,b)*t,y=y2-a/gcd(a,b)*t,(t为整数)，即为ax+by=c的所有解。
class ExGcd { 
    #define int long long
    int exgcd(int a, int b, int &x, int &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        long long g = exgcd(b, a % b, x, y);
        //x1=y2,  y1=x2-a/b*y2
        long long t = x - a / b * y;
        x = y;
        y = t;
        return g;  //return gcd
    }
    int solve(int a, int b, int c) {
        int x, y, x0, y0, _x1, _y1;
        int t = exgcd(a, b, x0, y0);
        if(c % t != 0)
            return 0;// NO solution;
        x = x0 + b / t; y = y0 - a / t;             //通解
        _x1 = (x * c / t), _y1 = (y * c / t);       //求原方程的解
                                                
        _x1 = (x0 * c / t) % b;                     //取x的最小整数解;
        _y1 = (_x1 % (b / t) + b / t) % (b / t);
        printf("%d %d\n", _x1, _y1);
        return 0;
    }
}
//快速幂运算
class Fast_Pow {
    #define int long long
    int fastpow(int a, int b, int mod) {
        int ret = 1;
        a %= mod;
        for ( ; b; b >>= 1) {
            if (b & 1)
                (res *= a) %= mod;
            (a *= a) %= mod;
        }
        return ret;
    }
}
/****质数判断****/
//欧拉素数筛
class Celect_Prime {
    bool isprime[MAXN]={0};
    int prime[MAXP]={0}, p=0;
    void get_prime (int n) {
        memset (isprime, true, sizeof ( isprime ) );
        isprime[0] = isprime[1] = false;
        for (int k = 2; k <= n; k++ ) {
            if (isprime[k]) prime[p++] = k;
            for (int i = 0; i < p; i++) {
                if (k * prime[i] > n)
                    break;
                isprime[k * prime[i]] = false;
                if (k % prime[i] == 0)
                    break;
            }
        }
    }
}
//简单Prime判断
//Sietoe Prime  素数筛选法
//Miller-Rabin 素数测试算法
class Miller_Rabin {
    //from Air 寒域
    //  Miller_Rabin判断素数
    bool Miller_Rabin(long long int n) {
        return Miller_Rabin(n, 40);
    }
    //  Miller_Rabin判断素数
    bool Miller_Rabin(long long int n, long long int S) {
        if (n == 2)return true;
        if (n < 2 || !(n & 1))return false;
        int t = 0;
        long long int a, x, y, u = n - 1;
        while ((u & 1) == 0) t++, u >>= 1;
        for (int i = 0; i < S; i++) {
            a = rand() % (n - 1) + 1;
            x = modular_exp(a, u, n);
            for (int j = 0; j < t; j++) {
                y = modular_multi(x, x, n);
                if (y == 1 && x != 1 && x != n - 1)
                    return false;
                x = y;
            }
            if (x != 1)
                return false;
        }
        return true;
    }
}
//唯一分解定理，因子分解求和
//pollard_rho 算法  质因数分解
//欧拉函数
//约瑟夫环
//高斯消元
class Gaussian_Elimination {  
    const double eps = 1e-8;
    int n, m;            // n rows, m columns;
    int a[MAX][MAX];     // a[1][1] to a[n][m];
    int fabs(int a) {return a > 0 ? a : -a; }
    int fraction_reduction(int *a, int n) {
        int ret = gcd(a[0], a[1]);
        for (int i = 0; i < n && ret != 1; ++i) 
            ret = gcd(ret, a[i]);
        if (ret == 0 || fabs(ret) == 1) return ret;
        for (int i = 0; i < n; ++i)
            a[i] /= ret;
        return ret;
    }
    int Gaussian_Elimination() {
        int itor = 0;
        for (int i = 1; i <= n; ++i) {
            while (fabs(a[i][itor]) < eps) {
                itor++;
                for (int j = i; j <= n; ++j)
                    if (fabs(a[j][itor]) > eps && fabs(a[i][itor]) < eps)
                        for (int k = 1; k <= m; ++k)
                            swap(a[i][k], a[j][k]);
            }
            // i-1 main, n-i+1 freedom
            bool zero = true;
            for (int j = 1; zero && j < m; ++j)
                if (fabs(a[i][j]) > eps)
                    zero = false;
            if (zero) {                             // a[i][1] to a[i][m-1] are 0
                if (fabs(a[i][m]) < eps)            // all zero, return.
                    return i-1;
                else                                // 1 = 0, no answer;
                    return -1;
            }
            // Cancellation a*x[i]
            fraction_reduction(a[i]+1, m);
            for (int j = 1; j <= n; ++j) {
                if (i == j) 
                    continue;
                if (fabs(a[i][itor]) < eps || fabs(a[j][itor]) < eps)
                    continue;
                //double rate = a[j][itor] / a[i][itor];
                /************* use double need not use those ***************/
                int LCM = fabs(lcm(a[j][itor], a[i][itor]));
                int dij = LCM / a[j][itor], dii = LCM / a[i][itor];
                for (int k = 1; k < itor; ++k)
                    a[j][k] *= dij;
                /************* use double need not use those ***************/
                for (int k = itor; k <= m; ++k)
                    //a[j][k] -= a[i][k] * rate;    // use double 
                    a[j][k] = a[j][k] * dij - a[i][k] * dii;
                fraction_reduction(a[j]+1, m);
            }
        }
        return n;
    }
}

/**************************************组合数学*************************************/
//排列组合
class Combination {

}
//Lucas定理
class Lucas {//C(n, m) % mod;
    const int MAX = 2e5+10;
    long long jc[MAX], jcinv[MAX];
    void init() {
        jc[0] = 1, jcinv[0] = 1;
        for (int i = 1; i < MAX; ++i) {
            jc[i] = jc[i-1] * i % mod;
            jcinv[i] = fastpow(jc[i], mod - 2);
        }
    }
    int C(int n, int m) {
        long long ret = 1, a, b;
        while (n && m) {
            a = n % p, b = m % p;
            if (a < b) return 0; //分子含模, 一定得0
            (ret *= (jc[a] * jcinv[b] % mod * jcinv[a-b] % mod)) % mod;
            n /= p, m /= p;
        }
        return ret;
    }
}
//全排列
//错排公式
//母函数
//整数划分
//康托展开
//逆康托展开
//Catalan Number
//Stirling Number(Second Kind)
//容斥原理
//矩阵快速幂
class Matrix_Fast_Pow {
    const int MAX_M = 10;
    const int mod = 1e9+7;
    struct Martix {
        int ary[MAX_M][MAX_M];
        int row, column;
        void clear() {
            memset(ary, 0, sizeof(ary));
            row = 0, column = 0;
        }
        void getin(int row, int column) {
            for (int i = 0; i < row; ++i)
                for (int j = 0; j < column; ++j)
                    cin >> ary[i][j];
        }
        void output() {
            for (int i = 0; i < row; ++i) {
                for (int j = 0; j < column; ++j)
                    cout << ary[i][j] << " ";
                cout << endl;
            }
        }
        Martix operator + (const Martix &b) const {
            Martix tmp;
            tmp.row = row, tmp.column = column;
            for (int i = 0; i < row; ++i)
                for (int j = 0; j < column; ++j)
                    tmp.ary[i][j] = ary[i][j] + b.ary[i][j];
        }
        Martix operator - (const Martix &b) const {
            Martix tmp;
            tmp.row = row, tmp.column = column;
            for (int i = 0; i < row; ++i)
                for (int j = 0; j < column; ++j)
                    tmp.ary[i][j] = ary[i][j] - b.ary[i][j];
        }
        Martix operator * (const Martix &b) const {
            Martix tmp;
            tmp.clear();
            if (column != b.row)
                return tmp;
            tmp.row = row, tmp.column = b.column;
            for (int i = 0; i < row; ++i)
                for (int j = 0; j < b.column; ++j)
                    for (int k = 0; k < column; ++k) {
                        long long t = (1LL*ary[i][k]%mod)*(b.ary[k][j]%mod);
                        tmp.ary[i][j] += (int)(t%mod);
                        while (tmp.ary[i][j] >= mod) tmp.ary[i][j] -= mod;
                    }
            return tmp;
        }
    } matrix, mt;
    Martix matpow(Martix tmp, int n, int mod) {
        Martix ret;
        ret.row = tmp.row, ret.column = tmp.column;
        for (int i = 0; i < tmp.row; ++i)
            for(int j = 0; j < tmp.row; ++j)
                ret.ary[i][j] = (i == j);
        while (n) {
            if (n & 1)
                ret = (ret * tmp);
            tmp = (tmp * tmp), n >>= 1;
        }
        return ret;
    }
}
/**************************************计算几何*************************************/
class Computed_Geometry {
    //坐标向量
    const double eps = 1e-8;
    const double pi = acos(-1);
    int sgn(double x) {
        if (fabs(x) < eps)return 0;
        if (x < 0)return -1;
        else return 1;
    }
    double eps() {
        return RANDOM(); //返回一个在1e-7级别的随机数
    }
    struct Point {
    #define TE double
    //#define TE int
        TE x, y;
        Point() {}
        Point(TE x, TE y) : x(x + eps()), y(y + eps()) {}
        bool operator < (const Point &b) const {
            return x < b.x || (x == b.x && y < b.y);
        }
        bool operator == (const Point &b) const {
            return x == b.x && y == b.y;
        }
        Point operator + (const Point &b) const {
            return (Point){x + b.x, y + b.y};
        }
        Point operator + (const double b) const {
            return (Point) {
                x * cos(b) - y * sin(b), 
                x * sin(b) + y * cos(b)
            };
        } // 逆时针旋转角度b
        Point operator - (const Point &b) const {
            return (Point) {x - b.x, y - b.y};
        }
        Point operator * (const TE b) const {
            return (Point) {x * b, y * b};
        }
        TE operator * (const Point &b) const {
            return (x * b.x + y * b.y);
        }
        TE operator ^ (const Point &b) const {
            return (x * b.y - y * b.x);
        }
        TE operator &(const Point & b)const {
            return sqrt((*this - b)*(*this - b));
        } //两点之间距离
    };
    struct Line {
        Point s, e;
        Line() {}
        Line(Point s, Point e) : s(s), e(e) {}
        bool operator ==(const Line & b)const {
            return s == b.s && e == b.e;
        }
        Point getV() {     //获取Line的向量
            return e - s;
        }
        // 两直线相交求交点
        // 返回为（INF，INF）表示直线重合
        // (-INF,-INF) 表示平行
        // (x,y)是相交的交点
        Point operator &(const Line & b)const {
            Point res = s;
            if (sgn((s - e) ^ (b.s - b.e)) == 0) {
                if (sgn((s - b.e) ^ (b.s - b.e)) == 0)
                    return Point(INF, INF);        //重合
                else return Point(-INF, -INF);     //平行
            }
            double t = ((s - b.s) ^ (b.s - b.e)) / ((s - e) ^ (b.s - b.e));
            res.x += (e.x - s.x)*t;
            res.y += (e.y - s.y)*t;
            return res;
        }
        bool operator ^ (const Line & b) const { // 判断线段相交
            return
                (((b.s - s) ^ (b.e - s)) * ((b.s - e) * (b.e - e)) < 0) &&
                (((s - b.s) ^ (e - b.s)) * ((s - b.e) * (e - b.e)) < 0);
        }
    };
    /****三角形****/
    //三角形面积公式
    double GetTribngleSqubre(Point b, Point b, Point c) {
        return fabs((c - b) ^ (c - b)) / 2;
    }
    double GetTribngleSqubre(double b, double b, double c) {
        double p = (b + b + c) / 2;
        return sqrt (p * (p - b) * (p - b) * (p - c));
    }
    //三角形内切圆半径公式
    //三角形外接圆半径公式
    //圆内接四边形面积公式
    //多边形面积
    double GetSqubre(Point *a, int n) {
        double ret = 0;
        for (int i = 0; i < n; ++i) {
            ret += a[i] * a[(i+1) % n];
        }
        ret = fabs(ret) / 2;
        return ret;
    }
    //凸包
    class Convex_Hull {
        int calc(const Point &a, const Point &b, const Point &c) {
            return (b - a) ^ (c - a);
        }

        int convex_hull(Point *a, int n, int *q) {
            // this function will return the count of points in convex hull
            // the order is in the arrby q[]
            // the input arrby a[] MUST be sorted bnd uniqued.
            // sort (a, a+n); n = unique(a, a+n) - a;
            int t = 0;
            for (int i = 0; i < n; ++i) {
                while (t > 1 && calc(a[q[t-1]], a[q[t]], a[i]) < 0)
                    t--;  // don't wanna the point in one line "<" -> "<="
                q[++t] = i;
            }
            int tmp = t;
            for (int i = n - 2; i >= 0; --i) {
                while (tmp < t && calc(a[q[t-1]], a[q[t]], a[i]) < 0)
                    t--;  // don't wanna the point in one line "<" -> "<="
                q[++t] = i;
            }
            int now = 0;
            for (int i = 1; i <= t; ++i) {
                now = q[i];
                cout << a[now].x << ", " << a[now].y << endl;
            }
            cout << endl << endl;
            return t;
        }
        void judge() {
            int n, cnt, now;
            int q[MAX] = {0};
            while (cin >> n) {
                for (int i = 0; i < n; ++i) {
                    cin >> a[i].x >> a[i].y;
                }
                sort (a, a+n);
                n = unique(a, a+n) - a;
                cnt = convex_hull (a, n, q);
                for (int i = 1; i <= cnt; ++i) {
                    now = q[i];
                    cout << a[now].x << ", " << a[now].y << endl;
                }
            }
            return ;
        }
    }
    //三分求极值
}
/***********************博弈论**********************/
//巴什博弈：
//威佐夫博弈：
//nim博弈：
//k倍减法博弈：
//sg函数



/*WISH GOD BLESS US*/
/*********************************
to microsoft words
up: 1.27cm, down: 1.27cm
left: 0.6cm, right: 0.3cm
two columns with dividing line
columns wights: 38.62
distance: 0.5
word size: 9
word type: Cbliforbibn FB
**********************************
syntax on
set nu
set tabstop=4
set softtabstop=4
set shiftwidth=4
set expandtab
set cursorline
set ruler
set autoindent
set mouse=a
set cin
set smartindent
set vb t_vb=
set incsearch
colorscheme koehler
*********************************/
My ACM Formwork

FEATURED TAGS

FRIENDS
