记录编号	366804	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2016]颓废元	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-01-25 23:24:36	内存使用	0.66 MiB

#include <cmath>
#include <stack>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=1010;
const int maxm=8500;
struct Edge{
	int from,next,to,flow;
}e[maxm],re[maxm];
int len,head[maxn],cur[maxn];
int S,T,n,m;
void Insert(int x,int y,int flow){
	len++;
	e[len].from=x;e[len].to=y;e[len].next=head[x];
	e[len].flow=flow;head[x]=len;
}
void Add_edge(int x,int y,int flow){
	Insert(x,y,flow);Insert(y,x,0);
}
int deep[maxn],Head,Tail,q[maxn],ansflow;
bool Bfs(){
	Head=Tail=0;q[Tail++]=S;
	memset(deep,-1,sizeof(deep));deep[S]=1;
	while(Head^Tail){
		int k=q[Head++];
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(deep[j]<0 && e[i].flow>0){
				deep[j]=deep[k]+1;
				q[Tail++]=j;
			}
		}
	}
	if(deep[T]<0)return false;
	return true;
}
#define ex(x) ( x&1 ? x+1 : x-1 )
int Dfs(int x,int flow){
	if(x==T || !flow)return flow;
	int tot=0;
	for(int &i=cur[x];i && flow;i=e[i].next){
		int j=e[i].to;
		if(deep[j]==deep[x]+1 && e[i].flow>0){
			int dd=Dfs(j,min(flow,e[i].flow));
			e[i].flow-=dd;e[ex(i)].flow+=dd;
			flow-=dd;tot+=dd;
			if(!flow)break;
		}
	}
	return tot;
}
void Maxflow(){
	ansflow=0;
	while(Bfs()){
		memcpy(cur,head,sizeof(head));
		ansflow+=Dfs(S,Inf);
	}
}
int Dfn[maxn],Low[maxn],Time,Belong[maxn],cnt;
bool flag[maxn];
stack<int> Q;
void Dfs(int x){
	Low[x]=Dfn[x]=++Time;flag[x]=true;Q.push(x);
	for(int i=head[x];i;i=e[i].next)if(e[i].flow){
		int j=e[i].to;
		if(!Dfn[j]){
			Dfs(j);
			Low[x]=min(Low[x],Low[j]);
		}
		else if(flag[j])Low[x]=min(Low[x],Dfn[j]);
	}
	if(Low[x]==Dfn[x]){
		cnt++;int k;
		do{
			k=Q.top();Q.pop();
			flag[k]=false;Belong[k]=cnt;
		}while(k!=x);
	}
}
int ANS[maxm],Flow[maxm];
void Init();
int main(){
	freopen("JJandLazy.in","r",stdin);freopen("JJandLazy.out","w",stdout); 
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	S=1;T=n;
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Add_edge(x,y,z);
	}memcpy(re,e,sizeof(e));
	Maxflow();
	for(int i=1;i<=m;i++)Flow[i]=e[i*2-1].flow;
	for(int i=1;i<=n;i++)if(!Dfn[i])Dfs(i);
	int num;scanf("%d",&num);
	for(int i=1;i<=num;i++){
		int type,x;scanf("%d%d",&type,&x);
		int fr=e[x*2-1].from,to=e[x*2-1].to;
		if(type==1){
			if(Flow[x]==0 && Belong[fr]!=Belong[to])puts("1");
			else puts("0");
		}
		else {
			if(Flow[x]==0 && Belong[fr]==Belong[S] && Belong[T]==Belong[to])puts("1");
			else puts("0");
		}
	}
	printf("%d\n",ansflow);
	num=0;
	for(int i=1;i<=m;i++){
		int fr=e[i*2-1].from,to=e[i*2-1].to;
		if(Flow[i]==0 && Belong[fr]!=Belong[to]){
			if(Belong[fr]==Belong[S] && Belong[to]==Belong[T]){ANS[++num]=i;continue;}
			memcpy(e,re,sizeof(re));e[i*2-1].flow=0;
			Maxflow();
			bool fff=0;
			for(int j=1;j<=num;j++)if(e[ANS[j]*2-1].flow){fff=1;break;}
			if(!fff)ANS[++num]=i;
		}
	}
	for(int i=1;i<=num;i++)printf("%d ",ANS[i]);
	//printf("TIMEUSED=%.3lf ",(double)clock()/CLOCKS_PER_SEC);
}
/*
7 7
1 2 10
2 3 1
3 4 1
4 7 10
1 5 10
5 6 1
6 7 10
5
1 2
1 3
1 6
2 6
2 2
*/