如果把“我全都要”看作是我全不要的话，就可以用最小割解决啦
源点S，汇点T
我们试图让每个市民作为一个等待被割断的路径
把狗狗给市民：建边(S,i,1)，其中i是市民
把狗狗给守卫：建边(j,T,1)，其中j是守卫（也就是边）
市民要在路上所有边看到狗：建边(i,j,1)，其中i是市民，j是i经过的边
（众所周知，(!A)&(!B)==!(A|B)，所以要把两种选择串起来）
然而这样边数太多了，考虑倍增来优化建边
...反正就是倍增优化建边，流量给正无穷
最大流=最小割，跑个dinic就行了（要加当前弧优化不然会T）
然后考虑输出方案。一个边如果被割断了，那么它的残余容量就是0
所以我们来从Sdfs一下，如果能搜到某个人，说明他没有狗；如果能搜到某条边，又因为S和T不连通，说明这条边到T要被割断，说明它有狗
各种各样的数组开大一点又不会怀孕
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e4+,inf=0x3f3f3f3f; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Edge{
int b,l,ne;
}ek[maxn*];
int N,M,ekh[maxn*],kct=;
int egh[maxn],eg[maxn*][],ect=;
int dep[maxn*],fa[maxn][],id[maxn][],pct=;
int S=,T=,P[maxn];
int A[maxn],cur[maxn*];
bool flag[maxn*],B[maxn];
queue<int> q; inline void adeg(int a,int b){
eg[++ect][]=b;eg[ect][]=egh[a];egh[a]=ect;
}
inline void adek(int a,int b,int c){
// printf("!%d %d %d\n",a,b,c);
ek[++kct].b=b,ek[kct].l=c,ek[kct].ne=ekh[a],ekh[a]=kct;
ek[++kct].b=a,ek[kct].l=,ek[kct].ne=ekh[b],ekh[b]=kct;
} void dfs(int x){
for(int i=;fa[x][i]&&fa[fa[x][i]][i];i++){
fa[x][i+]=fa[fa[x][i]][i];
id[x][i+]=++pct;
adek(id[x][i+],id[x][i],inf);
adek(id[x][i+],id[fa[x][i]][i],inf);
}
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];
if(b==fa[x][]) continue;
fa[b][]=x;dep[b]=dep[x]+;
id[b][]=++pct;adek(id[b][],T,);
// printf("~%d %d\n",b,id[b][0]);
dfs(b);
}
} void buildlca(int x,int y,int p){
if(dep[x]<dep[y]) swap(x,y);
for(int i=log2(dep[x]-dep[y]);i>=&&dep[x]!=dep[y];i--){
if(dep[fa[x][i]]>=dep[y]){
adek(p,id[x][i],);
x=fa[x][i];
}
}
if(x==y) return;
for(int i=log2(dep[x]);i>=;i--){
if(fa[x][i]!=fa[y][i]){
adek(p,id[x][i],);adek(p,id[y][i],);
x=fa[x][i],y=fa[y][i];
}
}
adek(p,id[x][],);adek(p,id[y][],); } bool bfs(){
CLR(dep,);CLR(cur,-);
dep[S]=;q.push(S);
while(!q.empty()){
int p=q.front();q.pop();
// printf("!@#%d %d\n",p,dep[p]);
for(int i=ekh[p];i;i=ek[i].ne){
int b=ek[i].b;
if(dep[b]||!ek[i].l) continue;
dep[b]=dep[p]+;
q.push(b);
}
}
return dep[T];
} int dinic(int x,int y){
if(x==T) return y;
int tmp=y;
if(cur[x]==-) cur[x]=ekh[x];
for(int &i=cur[x];i;i=ek[i].ne){
// printf("%d %d\n",i,cur[x]);
int b=ek[i].b;
if(dep[b]!=dep[x]+||!ek[i].l) continue;
int re=dinic(b,min(ek[i].l,tmp));
ek[i].l-=re,ek[i^].l+=re;
tmp-=re;if(!tmp) break;
}return y-tmp;
} void getans(int x){
flag[x]=;
for(int i=ekh[x];i;i=ek[i].ne){
int b=ek[i].b;
if(!ek[i].l) continue;
if(!flag[b]) getans(b);
}
} int main(){
// freopen("768E.in","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<N;i++){
int a=rd(),b=rd();
adeg(a,b);adeg(b,a);
}
for(i=;i<=M;i++) P[i]=++pct;
dep[]=;dfs();
for(i=;i<=M;i++){
int a=rd(),b=rd();
adek(S,P[i],);
buildlca(a,b,P[i]);
}
int ans=,a=,b=;
while(bfs()) ans+=dinic(S,inf);
getans(S);
for(i=;i<=M+;i++)
if(!flag[i]) A[++a]=i-;
for(i=;i<=N;i++)
if(flag[id[i][]]) B[i]=,b++;
printf("%d\n%d ",ans,a);
for(i=;i<=a;i++)
printf("%d ",A[i]);
printf("\n%d ",b);
for(i=;i<N;i++){
int x=eg[i<<][],y=eg[i<<|][];
if(fa[x][]!=y) swap(x,y);
// printf("!%d %d!\n",x,y);
if(B[x]) printf("%d ",i);
} return ;
}