Problem: ICP city has an express company whose trucks run from the crossing S to the crossing T. The president of the company is feeling upset because all the roads in the city are one-way, and are severely congested. So, he planned to improve the maximum flow (edge disjoint paths) from the crossing S to the crossing T by reversing the traffic direction on some of the roads.

Your task is writing a program to calculate the maximized flow from S to T by reversing some roads, and the list of the reversed roads.



Input

The first line of a data set contains two integers N (2 \leq N \leq 300) and M (0 \leq M \leq {\rm min} (1\,000,\ N(N-1)/2)). N is the number of crossings in the city and M is the number of roads.

The following M lines describe one-way roads in the city. The i-th line (1-based) contains two integers X_i and Y_i (1 \leq X_i, Y_i \leq N, X_i \neq Y_i). X_i is the ID number (1-based) of the starting point of the i-th road and Y_i is that of the terminal point. The last line contains two integers S and T (1 \leq S, T \leq N, S \neq T, 1-based).

The capacity of each road is 1. You can assume that i \neq j implies either X_i \neq X_j or Y_i \neq Y_j, and either X_i \neq Y_j or X_j \neq Y_i.

Output

In the first line, print the maximized flow by reversing some roads. In the second line, print the number R of the reversed roads. In each of the following R lines, print the ID number (1-based) of a reversed road. You may not print the same ID number more than once.

If there are multiple answers which would give us the same flow capacity, you can print any of them.

Examples

Input

2 1
2 1
2 1


Output

1
0


Input

2 1
1 2
2 1


Output

1
1
1


Input

3 3
3 2
1 2
3 1
1 3


Output

2
2
1
3

Solution (in JAVA):

Solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		IO io = new IO();
		int n = io.nextInt();
		int m = io.nextInt();
		int[] u = new int[m];
		int[] v = new int[m];
		for(int i=0;i<m;i++) {
			u[i] = io.nextInt() - 1;
			v[i] = io.nextInt() - 1;
		}
		int s = io.nextInt() - 1;
		int t = io.nextInt() - 1;
		Dinic g1 = new Dinic(n);
		for(int i=0;i<m;i++) {
			g1.addBidirectionalEdge(u[i], v[i], 1);
		}
		int f = g1.maximumFlow(s, t);
		MincostFlow g2 = new MincostFlow(n);
		for(int i=0;i<m;i++) {
			g2.addEdge(u[i], v[i], 1, 0, i+1);
			g2.addEdge(v[i], u[i], 1, 1, -(i+1));
		}
		int cost = g2.minCostFlow(s, t, f);
		ArrayList<Integer> ans = new ArrayList<>();
		for(ArrayList<MincostFlow.Edge> es: g2.g) {
			for(MincostFlow.Edge e: es) {
				if (e.cap0 != e.cap && e.id < 0) {
					ans.add(-e.id);
				}
			}
		}
		System.out.println(f);
		System.out.println(ans.size());
		for(int x: ans) {
			System.out.println(x);
		}
	}

}
class Dinic {
	public static final int INF = 1 << 29;
	private ArrayList<Edge>[] g;
	private int[] it;
	private int[] level;
	@SuppressWarnings("unchecked")
	public Dinic(int n) {
		g = new ArrayList[n];
		for(int i=0;i<n;i++) {
			g[i] = new ArrayList<>();
		}
		it = new int[n];
		level = new int[n];
	}
	public void addEdge(int from,int to,int cap) {
		g[from].add(new Edge(to,cap,g[to].size()));
		g[to].add(new Edge(from,0,g[from].size()-1));
	}
	public void addBidirectionalEdge(int from,int to,int cap) {
		addEdge(from,to,cap);
		addEdge(to,from,cap);
	}
	private void bfs(int s) {
		Arrays.fill(level, -1);
		Queue<Integer> q = new ArrayDeque<>();
		level[s] = 0;
		q.offer(s);
		while(!q.isEmpty()) {
			int v = q.poll();
			for(Edge e: g[v]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.offer(e.to);
				}
			}
		}
	}
	private int dfs(int v,int t,int f) {
		if (v == t) {
			return f;
		}
		for(;it[v]<g[v].size();it[v]++) {
			Edge e = g[v].get(it[v]);
			if (e.cap <= 0 || level[v] >= level[e.to]) {
				continue;
			}
			int d = dfs(e.to,t,Math.min(f,e.cap));
			if (d <= 0) {
				continue;
			}
			e.cap -= d;
			g[e.to].get(e.rev).cap += d;
			return d;
		}
		return 0;
	}
	public int maximumFlow(int s,int t) {
		int flow = 0;
		while(true) {
			bfs(s);
			if (level[t] < 0) {
				return flow;
			}
			Arrays.fill(it, 0);
			int f;
			while((f = dfs(s,t,INF)) > 0) {
				flow += f;
			}
		}
	}
	class Edge {
		int to,cap,rev;
		public Edge(int to,int cap,int rev) {
			this.to = to;
			this.cap = cap;
			this.rev = rev;
		}
	}
}
class MincostFlow {
	public static final int INF = 1<<29;
	int n;
	ArrayList<Edge>[] g;
	int[] h;
	int[] dist;
	int[] prevv;
	int[] preve;

	@SuppressWarnings("unchecked")
	public MincostFlow(int n) {
		this.n = n;
		g = new ArrayList[n];
		dist = new int[n];
		prevv = new int[n];
		preve = new int[n];
		h = new int[n];
		for(int i=0;i<n;i++) {
			g[i] = new ArrayList<MincostFlow.Edge>();
		}
	}

	public void addEdge(int from,int to,int cap,int cost,int id) {
		g[from].add(new Edge(to,cap,cost,g[to].size(),id));
		g[to].add(new Edge(from,0,-cost,g[from].size()-1,0));
	}

	/* F E log V */
	public int minCostFlow(int s,int t,int f) {
		int res = 0;
		Arrays.fill(h, 0);
		while(f > 0) {
			PriorityQueue<Pair> q = new PriorityQueue<Pair>();
			Arrays.fill(dist, INF);
			dist[s] = 0;
			q.offer(new Pair(0,s));
			while(!q.isEmpty()) {
				Pair p = q.poll();
				int v = p.v;
				if (dist[v] < p.dist) {
					continue;
				}
				for(int i=0;i<g[v].size();i++) {
					Edge e = g[v].get(i);
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						q.offer(new Pair(dist[e.to], e.to));
					}
				}
			}
			if (dist[t] == INF) {
				return -1;
			}
			for(int v = 0; v < n; v++) {
				h[v] += dist[v];
			}
			int d = f;
			for(int v = t; v != s; v = prevv[v]) {
				d = Math.min(d, g[prevv[v]].get(preve[v]).cap);
			}
			f -= d;
			res += d * h[t];
			for(int v = t; v != s;v = prevv[v]) {
				Edge e = g[prevv[v]].get(preve[v]);
				e.cap -= d;
				g[v].get(e.rev).cap += d;
			}
		}
		return res;
	}

	static class Edge {
		int to,cap,cost,rev;
		int cap0,id;
		public Edge(int to,int cap,int cost,int rev,int id) {
			this.to = to;
			this.cap = cap;
			this.cap0 = cap;
			this.cost = cost;
			this.rev = rev;
			this.id = id;
		}
	}
	static class Pair implements Comparable<Pair>{
		int dist,v;
		public Pair(int dist,int v) {
			this.dist = dist;
			this.v = v;
		}
		public int compareTo(Pair p) {
			return Integer.compare(this.dist, p.dist);
		}
	}
}
class IO extends PrintWriter {
	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public IO() { this(System.in);}
	public IO(InputStream source) { super(System.out); this.in = source;}
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();}
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public char[] nextCharArray(int len) {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		char[] s = new char[len];
		int i = 0;
		int b = readByte();
		while(isPrintableChar(b)) {
			if (i == len) {
				throw new InputMismatchException();
			}
			s[i++] = (char) b;
			b = readByte();
		}
		return s;
	}
	public String nextLine() {
		if (!hasNextLine()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(!isNewLine(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public char nextChar() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		return (char) readByte();
	}
	public double nextDouble() { return Double.parseDouble(next());}
	public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
	public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
	public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
	public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
	public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}
	public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
	public void close() { super.close(); try {in.close();} catch (IOException e) {}}
}