cos

void TopSort() {
	int cnt = 0;
    for(圖中的每個頂點V) 
		if( Indegree[W] == 0)
			Enqueue(V,Q);
	while(!isEmpty(Q)) {
		V = Dequeue(Q);
		輸出V,或記錄V的輸出序號,cnt++;
        for(V的每個鄰接點W)
        	if(--Indegree[W] == 0)
	            Enqueue(V,Q);
	}
	if(cnt != |V|)
		Error("圖中有回路");
}

const int maxn = 1005;
int N,M;//頂點數、邊數（活動數）
int edge[maxn][maxn];
int mint[maxn];//到每個活動檢查點的最短時間
int In[maxn];//每個活動檢查點的入度
void init() {
    memset(edge, -1, sizeof(edge));
    memset(mint, 0, sizeof(mint));
    memset(In, 0, sizeof(In));
}
bool Topsort() {//拓撲排序
    queue<int> q;
    for(int i = 0; i < N; ++i) {
        if(In[i] == 0) 
            q.push(i);
    }
    int cnt = 0;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        cnt++;
        for(int i = 0; i < N; ++i) {
            if(v == i || edge[v][i] == -1) continue;//檢查以v為起點的所有邊
            In[i]--;
            //其他操作
            if(In[i] == 0) q.push(i);
        }
    }
    if(cnt != N) return false;
    else return true;
}

void X_Sort(ElementType A[], int N);

void Bubble_Sort(ll a[], int N) {
    for(int P = N-1; P >= 0; P--) {
        bool flag = false;
        //一趟冒泡 從上往下比較，上邊大於下邊則交換
        for(int i = 0; i < P; ++i) {    
            if(a[i] > a[i+1]) {
                swap(a[i], a[i+1]);
                flag = true;
            }
        }
        if(!flag) break; //一趟下來已經有序了，未發生交換
    }
}

void Insertion_Sort(ll a[], int N) {
    for(int P = 1; P < N; P++) {
        ll t = a[P];//摸下一張牌
        int i;
        for(i = P; i > 0 && a[i-1] > t; --i) 
            a[i] = a[i-1];  //移出空位 直到前面那個這個元素小於當前元素
        a[i] = t;   //新牌落位
    }
}

void Shell_Sort(ll a[], int N) {
    for(int D = N/2; D > 0; D /= 2) { //希爾增量序列
        for(int P = D; P < N; ++P) { //插入排序
            ll t = a[P];
            int i;
            for(i = P; i >= D && a[i-D] > t; i -= D) 
                a[i] = a[i-D];
            a[i] = t;
        }
    }
}

void Selection_Sort(ll a[], int N) {
    for(int i = 0; i < N; ++i) {
        int mini = 0;
        ll ans = inf;
        //找i後邊的最小元 並將其位置賦給mini
        for(int j = i; j <= N-1; ++j) {
            if(a[j] < ans) {
                ans = a[j];
                mini = j;
            }
        }
        //將未排序部分的最小元換到有序部分的最後位置
        swap(a[i], a[mini]);
    }
}

void swap(ll& x, ll& y) {
    ll t = x;
    x = y;
    y = t;
}
void PercDown(ll a[], int N, int rt) {
    //將N個元素的數組中以a[now]為根的子堆調整為最大堆
    int father, son;
    ll tmp = a[rt];
    for(father = rt; (father*2+1) < N; father = son) {
        son = father * 2 + 1;//左兒子
        if(son != N-1 && a[son] < a[son+1]) //右兒子存在且比左兒子大
            son++;
        if(tmp >= a[son]) break;//找到該放的地方
        else a[father] = a[son];//下濾
    }
    a[father] = tmp;
}
inline void BuildHeap(ll a[], int N) {
    for(int i = N/2-1; i >= 0; --i) {
        PercDown(a, N, i);
    }
}
void Heap_Sort(ll a[], int N) {
    BuildHeap(a, N);
    for(int i = N-1; i > 0; --i) {
        swap(a[0], a[i]);//最大堆頂a[0]與a[i]交換
        PercDown(a, i, 0);//刪除後進行調整
    }
}

void Merge(ll a[], int s, int m, int e, ll tmp[]) {
    //將數組a的局部a[s,m]和a[m+1,e]合併到數組tmp,並保證tmp有序
    //然後再拷貝回a[s,m]  時間複雜度O(e-m+1),即O(n);
    int pb = s;//pb為tmp數組的下標
    int p1 = s, p2 = m+1;//p1指向前一半p2指向後一半
    while (p1 <= m && p2 <= e) {
        if (a[p1] < a[p2])
            tmp[pb++] = a[p1++];
        else 
            tmp[pb++] = a[p2++];
    }
    while(p1 <= m) 
        tmp[pb++] = a[p1++];
    while(p2 <= e) 
        tmp[pb++] = a[p2++];
    for (int i = 0; i < e-s+1; ++i)
        a[s+i] = tmp[i];
}
void MergeSort(ll a[], int s, int e, ll tmp[]) {
    if (s < e) {//若s>=e則不做任何事情
        int m = s + (e-s)/2;
        MergeSort(a, s, m, tmp);//前一半排序
        MergeSort(a, m+1, e, tmp);//后一半排序
        Merge(a, s, m, e, tmp);//合併 將a中s到m和m+1到e的兩個數組有序的合併
    }
}

void QuickSort(ll a[], int s, int e){//將a[s,e]快排
    if (s >= e)
        return;
    int k = a[s];
    int i = s,j = e;
    while (i != j) {
        while (j > i && a[j] >= k)  --j;
        swap(a[i],a[j]);
        while (i < j && a[i] <= k)  ++i;
        swap(a[i],a[j]);
    }//處理完後a[i] = k;
    QuickSort(a, s, i-1);//快排左邊部分
    QuickSort(a, i+1, e);//快排右邊部分
}

ll getMax(ll a[], int n) {//找n個元素的a數組中最大數
    int maxx = a[0];
    for(int i = 1; i < n; ++i) {
        if(a[i] > maxx) maxx = a[i];
    }
    return maxx;
}
void radixsort(ll a[], int n, int exp) { //對n個元素的數組a按照"某位數"進行排序(桶排序),基數為10
    ll tmp[maxn];
    ll T[20] = {0}; //有負數的十進制 二十個桶
    for(int i = 0; i < n; ++i) //T存儲該桶里有多少個數
        T[(a[i]/exp)%10 + 10]++;
    for(int i = 1; i < 20; ++i) //讓T的值是在tmp中的位置
        T[i] += T[i-1];
    for(int i = n - 1; i >= 0; --i) {
        int now = T[(a[i]/exp)%10 + 10];//當前這個數所應在的位置
        tmp[now-1] = a[i];
        T[(a[i]/exp)%10 + 10]--;
    }
    for(int i = 0; i < n; ++i)
        a[i] = tmp[i]; //將排好序的tmp賦給a
}
void Radix_Sort(ll a[], int n) {
    ll maxnum = getMax(a, n);
    for(int exp = 1; maxnum/exp > 0; exp *= 10) 
        radixsort(a, n, exp);
}