template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
    while (!Q.empty()) Q.pop();
}

// it destroys queue
void showQueue(priority_queue<edge, vector< edge >, compareWeights> queue) {
	while (!queue.empty()) {
		cout << queue.top().v << "-" << queue.top().u << ":" << queue.top().w << endl;
		queue.pop();
	}
}

int medianaSubarreglo(int prox, priority_queue<int>& menores, priority_queue<int, vector<int>, greater<int> >& mayores)
{
	
	if (menores.empty())
	{
		menores.push(prox);
	}
	else
	{
		if (prox < menores.top())
		{
			if (menores.size() > mayores.size())
			{
				mayores.push( menores.top() );
				menores.pop();
				menores.push(prox);
			}
			else
			{
				menores.push(prox);
			}
		}
		else
		{
			if (mayores.size() > menores.size())
			{
				menores.push( mayores.top() );
				mayores.pop();
				mayores.push(prox);
			}
			else
			{
				mayores.push(prox);
			}			
		}
	}

	// cout << prox << endl;

	if (menores.size() > mayores.size())
		return menores.top();
	if (menores.size() < mayores.size())
		return mayores.top();
	if (menores.size() == mayores.size())
		return (menores.top()+mayores.top())/2;

}

bool getAns(priority_queue<Node>& heapOne, vector<Edge>&edgeOne) {
    deque<Node> queOne;
    int i,num;

    while(!heapOne.empty()) {
        now = heapOne.top();
        heapOne.pop();
        num = now.du;

        if(num > heapOne.size()) {
            return false;
        }

        for(i=0; i<num; i++) {
            queOne.push_back(heapOne.top());
            heapOne.pop();
        }

        if(ok && !heapOne.empty()) {
            ok = false;
            heapTwo = heapOne;
            deque<Node> queTwo = queOne;
            edgeTwo = edgeOne;

            heapNode = heapTwo.top();
            heapTwo.pop();

            dequeNode = queTwo.back();
            queTwo.pop_back();

            heapTwo.push(dequeNode);
            queTwo.push_back(heapNode);

            while(!queTwo.empty()) {
                dequeNode = queTwo.back();
                queTwo.pop_back();
                edgeTwo.push_back(Edge(now.pos, dequeNode.pos));
                if(dequeNode.du > 1) {
                    dequeNode.du--;
                    heapTwo.push(dequeNode);
                }
            }
            if(!getAns(heapTwo, edgeTwo)) {
                ok = true;
            }
        }
        while(!queOne.empty()) {
            dequeNode = queOne.back();
            queOne.pop_back();
            edgeOne.push_back(Edge(now.pos, dequeNode.pos));
            str[now.pos][dequeNode.pos] = str[dequeNode.pos][now.pos] = 1;
            if(dequeNode.du > 1) {
                dequeNode.du--;
                heapOne.push(dequeNode);
            }
        }

    }
    return true;
}

 REP(i, MAXN) {
     mm[i][MAXN - 1] = num[i][MAXN - 1];
     pq.push(state(i, MAXN - 1, num[i][MAXN - 1]));
 }

void init()
{
	int i,j,k;
	scanf("%d",&M);

	while( !heap.empty() ) heap.pop();

	//初始化
	for (i=1;i<=N;++i) 
	{
		dis[i]=INFINITE;
		visit[i]=false;
		path[i]=0;
		bian[i][0]=0;
		for (j=1;j<=N;++j) map[i][j]=INFINITE;
	}

	//读入信息
	for (k=1;k<=M;++k)
	{
		scanf("%d%d",&i,&j);
		scanf("%d",&map[i][j]);
		map[j][i]=map[i][j];

		bian[i][0]++;
		bian[j][0]++;
		bian[i][bian[i][0]]=j;
		bian[j][bian[j][0]]=i;
	}

	//堆初始化
	dis[2]=0;
	path[2]=1;
	node temp;
	temp.dist=0;
	temp.ID=2;
	heap.push(temp);

	int l;
	while (true)
	{
		//从堆中找出最小距离
		while (!heap.empty() && visit[heap.top().ID]) heap.pop();
		if (heap.empty()) break;

		k=heap.top().ID;
		dis[k]=heap.top().dist;
		heap.pop();

		visit[k]=true;
		for (j=1;j<=bian[k][0];++j) 
		{
			l=bian[k][j];
			//满足松弛操作，加入堆
			if (dis[k]+map[k][l]<dis[l]) 
			{
				dis[l]=dis[k]+map[k][l];
				temp.ID=l;
				temp.dist=dis[l];
				heap.push(temp);
			}
			//DP计算方案
			if (visit[l] && dis[l]<dis[k]) path[k]+=path[l];
		}

	}

	printf("%d\n",path[1]);
}

void init(){
    for(int i=0;i<MAX_V;i++) G[i].clear();
    while(!que.empty()) que.pop();
}

void insert(int x) {
    if(queue_b.empty()) {
        queue_b.push(x);
    }
    else{
      if(x > queue_b.top())
        queue_b.push(x);
      else
        queue_s.push(x);
    }
    if(queue_b.size() < queue_s.size() ) {
        queue_b.push(queue_s.top());
        queue_s.pop();
    }
    if(queue_b.size() > queue_s.size() + 1) {
        queue_s.push(queue_b.top());
        queue_b.pop();
    }
}

void update(int pos)
{
	que.push(make_pair(tot[pos],pos));
}

	size_t const current() const { return q.size(); }

int main()
{
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

    init();

    int res = game(h, t);

    if (res == 0)
    {
        puts("Draw");
        return 0;
    }

    if (res == 1) puts("Ivan");
    if (res == 2) puts("Zmey");

    if (res == 2)
    {
        int res2 = rec(h, t, res);
        printf("%d\n", res2);
    } else {
        q.push(make(0, h, t));
        dp[h][t] = 0;
        while (!q.empty())
        {
            piii cur = q.top();
            q.pop();
            int x = cur.second.first;
            int y = cur.second.second;

            if (x + y > R) continue;

            int w = cur.first;
            if (dp[x][y] != w) continue;

            int lim = min(x, n);
            for (int i = 1; i <= lim; ++i)
            {
                int dx = H[i].first;
                int dy = H[i].second;
                int nx = x - i + dx;
                int ny = y + dy;

                if (dp[nx][ny] == -1 || dp[nx][ny] > dp[x][y] + 1)
                {
                    dp[nx][ny] = dp[x][y] + 1;
                    q.push(make(dp[nx][ny], nx, ny));
                }
            }

            lim = min(y, m);
            for (int i = 1; i <= lim; ++i)
            {
                int dx = T[i].first;
                int dy = T[i].second;
                int nx = x + dx;
                int ny = y - i + dy;

                if (dp[nx][ny] == -1 || dp[nx][ny] > dp[x][y] + 1)
                {
                    dp[nx][ny] = dp[x][y] + 1;
                    q.push(make(dp[nx][ny], nx, ny));
                }
            }
        }

        printf("%d\n", dp[0][0]);
    }
    return 0;
}

int main() {
    int N;
    int ans = 0;
    int size = 0;
    scanf("%d", &N);
    while(N--) {
        int type;
        scanf("%d", &type);
        if(type == 2) {
            if(ans) printf("%d\n", ans);
            else puts("No reviews yet");
        } else {
            int x;
            scanf("%d", &x);
            switch(size) {
                case 0: 
                case 1: bad.push(x); break;
                case 2: bad.push(x); ans = bad.top(); bad.pop(); break;
                default: {
                    if (x > ans) {
                        good.push(x);
                        if(size % 3 != 2) {
                            bad.push(ans);
                            ans = good.top();
                            good.pop();
                        }
                    }
                    else {
                        bad.push(x);
                        if(size % 3 == 2) {
                            good.push(ans);
                            ans = bad.top();
                            bad.pop();
                        }
                    }
                }
            }
            ++size;
        }
    }
}

int main ( ) {
    while(scanf("%d %d", &v, &e) != EOF && v && e) {
        scanf("%d %d", &f, &t);
        for (int i = 0; i < e; i++) {
            scanf("%d %d %d", &a, &b, &w);
            ed.to = b;
            ed.from = a;
            ed.w = w;
            adj[a].push_back(ed);
            ed.to = a;
            ed.from = b;
            adj[b].push_back(ed);
        }
        for (int i = 0; i < v; i++) {
            verts[i].w = -1;
            verts[i].n = i;
        }
        verts[f].w = 0;
        fila.push(verts[f]);

        while (!fila.empty()) {
            nd = fila.top();
            fila.pop();

            for (int i = 0; i < adj[nd.n].size(); i++) {
                if (verts[adj[nd.n][i].to].w == -1 || verts[adj[nd.n][i].to].w > nd.w + adj[nd.n][i].w) {
                    verts[adj[nd.n][i].to].w = nd.w + adj[nd.n][i].w;
                    fila.push(verts[adj[nd.n][i].to]);
                }
            }
        }

        for (int i = 0; i < adj[t].size(); i++) {
            regr.push(adj[t][i]);
        }

        while (!regr.empty()) {
            ed = regr.front();
            regr.pop();
            
            if (ed.w != -1 && verts[ed.to].w + ed.w == verts[ed.from].w) {
                for (int i = 0; i < adj[ed.to].size(); i++) {
                    if (adj[ed.to][i].to = ed.from && adj[ed.to][i].w == ed.w) adj[ed.to][i].w = -1;
                    else regr.push(adj[ed.to][i]);
                }
                for (int i = 0; i < adj[ed.from].size(); i++) if (adj[ed.from][i].to = ed.to && adj[ed.from][i].w == ed.w) adj[ed.from][i].w = -1;
            }
        }
        for (int i = 0; i < v; i++) {
            printf("%d(%d) -> ", i, verts[i].w);
            for (int j = 0; j < adj[i].size(); j++) printf("%d(%d) ", adj[i][j].to, adj[i][j].w);
            printf("\n");
        }

        for(int i = 0; i < v; i++) verts[i].w = -1;

        fila.push(verts[f]);
        while (!fila.empty() ) {
            nd = fila.top();
            fila.pop();

            for (int i = 0; i < adj[nd.n].size(); i++) {
                if (adj[nd.n][i].w != -1 && (verts[adj[nd.n][i].to].w == -1 || verts[adj[nd.n][i].to].w > nd.w + adj[nd.n][i].w)) {
                    verts[adj[nd.n][i].to].w = nd.w + adj[nd.n][i].w;
                    if (adj[nd.n][i].to == t) goto endloop;
                    fila.push(verts[adj[nd.n][i].to]);
                }
            }
        }
endloop:
        printf("%d\n", verts[t].w);
        for (int i = 0; i < e; i++) adj[i].clear();

        while (!fila.empty()) fila.pop();
    }  
}

int main()
{
    int tc;
    scanf("%i\n", &tc);
    for(int i = 0; i < tc; i++)
    {
        int n;
        scanf("%i\n", &n);
        while(!asks.empty())
            asks.pop();
        while(!bids.empty())
            bids.pop();
        int stockPrice = -1;
        for(int j = 0; j < n; j++)
        {
            int numero;
            int precio;
            scanf("%s %i shares at %i", temp, &numero, &precio);
            string tipo(temp);
            bool compra = tipo == "buy";
            if(compra)
                bids.push(Oferta(numero, precio));
            else   
                asks.push(Oferta(numero, precio));
            while(!bids.empty() && !asks.empty() && bids.top().precio >= asks.top().precio)
            {
                Oferta bid = bids.top();
                Oferta ask = asks.top();
                bids.pop();
                asks.pop();
                if(bid.numero > ask.numero)
                {
                    bid.numero -= ask.numero;
                    bids.push(bid);
                }
                else if(bid.numero < ask.numero)
                {
                    ask.numero -= bid.numero;
                    asks.push(ask);
                }
                stockPrice = ask.precio;
            }
            if(bids.empty() && asks.empty())
            {
                if(stockPrice == -1)
                    printf("- - -\n");
                else
                    printf("- - %i\n", stockPrice);
            }
            else if(bids.empty())
            {
                if(stockPrice == -1)
                    printf("%i - -\n", asks.top().precio);
                else
                    printf("%i - %i\n", asks.top().precio, stockPrice);
            }
            else if(asks.empty())
            {
                if(stockPrice == -1)
                    printf("- %i -\n", bids.top().precio);
                else
                    printf("- %i %i\n", bids.top().precio, stockPrice);
            }
            else
            {
                if(stockPrice == -1)
                    printf("%i %i -\n", asks.top().precio, bids.top().precio);
                else
                    printf("%i %i %i\n", asks.top().precio, bids.top().precio, stockPrice);
            }
        }
    }
}

void init() {
    while(!pq.empty()) pq.pop();
    for(int i = 0; i <= maxn; i++) {
        pre[i] = i;
    }
}

void AwithTheManhattanDistanceHeuristic()
{

    int stateNum = 0;
    while(!PQ.empty())PQ.pop();

    Initstate.g=0;
    Initstate.h=getManhattanDistanceNum(Initstate);

    PQ.push(Initstate);

    printf("Expanding state:\n");
    Initstate.output();


    while (!PQ.empty())
    {
        if(PQ.size()>lenOfQueue){
            lenOfQueue = PQ.size();
        }

        stateNum++;
        Puzzle queueFront = PQ.top();
        PQ.pop();

        printf("g(n)=%d  " ,queueFront.g);
        printf("h(n)=%d  ",queueFront.h);
        outputExpanding(queueFront);

        if(judgeComplete(queueFront))
        {
            break;
        }
        else
        {
            Puzzle tPuzzle = queueFront;
            if(tranform(LEFT,tPuzzle)&&!judgeSame(tPuzzle,queueFront))
            {
                tPuzzle.g = queueFront.g+1;
                tPuzzle.h = getManhattanDistanceNum(tPuzzle);
                giveFatherValue(tPuzzle,queueFront);
                PQ.push(tPuzzle);
                stateNum++;
            }
            tPuzzle = queueFront;
            if(tranform(RIGHT,tPuzzle)&&!judgeSame(tPuzzle,queueFront))
            {
                tPuzzle.g = queueFront.g+1;
                tPuzzle.h = getManhattanDistanceNum(tPuzzle);
                giveFatherValue(tPuzzle,queueFront);
                PQ.push(tPuzzle);
                stateNum++;
            }
            tPuzzle = queueFront;
            if(tranform(UP,tPuzzle)&&!judgeSame(tPuzzle,queueFront))
            {
                tPuzzle.g = queueFront.g+1;
                tPuzzle.h = getManhattanDistanceNum(tPuzzle);
                giveFatherValue(tPuzzle,queueFront);
                PQ.push(tPuzzle);
                stateNum++;
            }
            tPuzzle = queueFront;
            if(tranform(DOWN,tPuzzle)&&!judgeSame(tPuzzle,queueFront))
            {
                tPuzzle.g = queueFront.g+1;
                tPuzzle.h = getManhattanDistanceNum(tPuzzle);
                giveFatherValue(tPuzzle,queueFront);
                PQ.push(tPuzzle);
                stateNum++;
            }
        }
    }
    printf("%d\n",stateNum);


}

int main(){
    int n,l,i,bl;
    scanf("%d%d",&n,&l);
    for(i=0;i<l;i++){
        //scanf("%d",&b[i]);
        b[i]=scanInt();
        maxq.push(b[i]);
        minq.push(b[i]);
    }
    if(maxq.top()-minq.top()+1==l) ans++;
    bl=0;
    while(i<n){
        black[b[bl]]=1;
        //scanf("%d",&b[i]);
        b[i]=scanInt();
        maxq.push(b[i]);
        minq.push(b[i]);
        while(black[maxq.top()])
            maxq.pop();
        while(black[minq.top()])    
            minq.pop();
        if(maxq.top()-minq.top()+1==l) ans++;
        bl++;
        i++;
    }
    printf("%d",ans);
    return 0;
}

int main(){

	int t;
	inp(t);
	while(t--){
		memset(g,0, sizeof g);
		memset(visit,0, sizeof visit);
		inp(n);
		for(int i = 1; i <= n; i++){
			int nv;
			inp(nv);
			for(int j = 0; j < nv; j++){
				int neigh;
				inp(neigh);
				g[neigh][i] = 1;
			}
		}
		
		while(!desc.empty())
			desc.pop();
		
		timer = 0;
		
		for(int i = 1; i <= n; i++){
			if(visit[i] == 0)
				dfs(i);
		}

		memset(scc,0,sizeof scc);
		memset(visit,0,sizeof visit);
		int count = 0;
		while(!desc.empty()){
			int i = (desc.top()).second;
			desc.pop();
			if(visit[i] == 0){
				count++;
				redfs(i, count);
			}
		}

		int inedge[1001];
		memset(inedge,0,sizeof inedge);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(g[i][j] == 1 && scc[i] != scc[j]){
					inedge[scc[j]] = 1;
				}
			}
		}
		// for(int i = 1; i <= n; i++)
		// 	cout << scc[i] << endl;
		int zin = 0;
		int cone;
		for(int i = 1; i <= count; i++){
			if(inedge[i] == 0){
				zin++;
				cone = i;
			}
		}

		if(zin == 1){
			int setpl = 0;
			for(int i = 1; i <= n; i++){
				if(scc[i] == cone){
					setpl++;
				}
			}
			printf("%d\n", setpl);
		}
		else{
			printf("0\n");
		}

	}

	return 0;	
}

int main()
{
	int hh, mm, ss, viptag, index, nowtime;
	node temp;
	pair<int, int> tplayer;

	cin >> N;
	play_time.resize(N);
	is_vip_player.resize(N);
	for (int i = 0; i != N; ++i)
	{
		scanf("%d:%d:%d %d %d", &hh, &mm, &ss, &play_time[i], &viptag);
		is_vip_player[i] = (bool)viptag;
		play_time[i] = 60 * min(play_time[i], 120);
		temp.time = hh*3600 + mm*60 + ss;
		temp.id = i;
		temp.type = 1;
		affairs.push(temp);
	}

	cin >> K >> M;
	nums.resize(K);
	is_vip_table.resize(K);
	for (int i = 0; i != M; ++i)
	{
		cin >> index;
		is_vip_table[--index] = true;
	}
	for (int i = 0; i != K; ++i)
	{
		if (is_vip_table[i])
		{
			vip_table.insert(i);
		}
		else
		{
			ord_table.insert(i);
		}
	}

	while (!affairs.empty())
	{
		temp = affairs.top();
		affairs.pop();
		nowtime = temp.time;
		if (nowtime >= close_time)
		{
			break;
		}

		if (0 == temp.type)
		{
			freeTable(temp.id);
			/* 多个桌子可能同时释放*/
			while (!affairs.empty() && affairs.top().type == 0 && affairs.top().time == nowtime)
			{
				freeTable(affairs.top().id);
				affairs.pop();
			}

			while (!vip_table.empty() && !vip_player.empty())
			{
				temp.time = nowtime + vip_player.begin()->second;
				temp.type = 0;
				temp.id = *vip_table.begin();
				++nums[temp.id];
				printTime(vip_player.begin()->first, nowtime);
				affairs.push(temp);
				vip_table.erase(vip_table.begin());
				vip_player.erase(vip_player.begin());
			}

			while ((!ord_player.empty() || !vip_player.empty()) && (!ord_table.empty() || !vip_table.empty()))
			{
				tplayer = getPlayer();
				temp.time = nowtime + tplayer.second;
				temp.type = 0;
				temp.id = getTable();
				++nums[temp.id];
				printTime(tplayer.first, nowtime);
				affairs.push(temp);
			}
		}
		else
		{
			if (is_vip_player[temp.id])
			{
				if (!vip_table.empty())
				{
					temp.time = nowtime + play_time[temp.id];
					printTime(nowtime, nowtime);
					temp.type = 0;
					temp.id = *vip_table.begin();
					++nums[temp.id];
					affairs.push(temp);
					vip_table.erase(vip_table.begin());
				}
				else
				{
					if (!ord_table.empty())
//.........这里部分代码省略.........

void dijkstra(int x, int y, int d) {
    if (x >= 0 && y >= 0 && x < C && y < R && t[y][x] == -1 && lab[y][x] != '#') {
        t[y][x] = t[j][i] + d;
        q2.push(make_pair(-t[y][x], make_pair(x, y)));
    }
}