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 CPP):

Solution:
/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using graph = vector<vector<int>>;
using wgraph = vector<vector<pair<int, long long int>>>;
long long int INF = 1001001001001001LL;
int inf = 100100100;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define drep(i,n) for(int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(int i = s; i < t; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/


// verified : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A
// O(E V^2)

// [使い方]
// add_edge(from, to, cap) :  from から to へ 容量 cap の辺を貼る
// max_flow(s, t) :  s から t への最大フローを返す

template< typename T >
struct Dinic{
    const T inf;

    struct edge{
        int to;
        T cap;
        int rev;
        bool isrev;
    };

    vector<vector<edge>> g;
    vector<int> min_cost, iter;

    Dinic(int V) : inf(numeric_limits<T>::max()), g(V){}


    // 0-indexed
    void add_edge(int from, int to, T cap){
        g[from].emplace_back((edge){to, cap, (int)g[to].size(), false});
        g[to].emplace_back((edge){from, 0, (int)g[from].size() - 1, true});
    }

    bool bfs(int s, int t) {
        min_cost.assign(g.size(), -1);
        queue<int> que;
        min_cost[s] = 0;
        que.push(s);
        while(!que.empty() && min_cost[t] == -1){
            int p = que.front();
            que.pop();
            for(auto &e : g[p]) {
                if(e.cap > 0 && min_cost[e.to] == -1){
                    min_cost[e.to] = min_cost[p] + 1;
                    que.push(e.to);
                }
            }
        }
        return min_cost[t] != -1;
    }
    
    T dfs(int idx, const int t, T flow){
        if(idx == t) return flow;
        for(int &i = iter[idx]; i < g[idx].size(); i++){
            edge &e = g[idx][i];
            if(e.cap > 0 && min_cost[idx] < min_cost[e.to]){
                T d = dfs(e.to, t, min(flow, e.cap));
                if(d > 0){
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    // 0-indexed
    T max_flow(int s, int t){
        T flow = 0;
        while(bfs(s, t)){
            iter.assign(g.size(), 0);
            T f = 0;
            while((f = dfs(s, t, inf)) > 0) flow += f;
        }

        return flow;
    }
    
    void output(vector<vector<int>> &A) {
        for(int i = 0; i < g.size(); i++) {
            for(auto &e : g[i]) {
                if(e.isrev) continue;
                auto &rev_e = g[e.to][e.rev];
                //cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
                if(rev_e.cap == 1) A[i][e.to] = 1;
            }
        }
    }
};

int main() {
  int n, m; cin >> n >> m;

  Dinic<int> dc(n);
  set<pair<int, int>> st;
  map<pair<int, int>, int> mp;

  for(int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    u--;
    v--;
    st.insert({u, v});
    mp[make_pair(u, v)] = i + 1;
    dc.add_edge(u, v, 1);
    dc.add_edge(v, u, 1);
  }
  

  int s, t; cin >> s >> t;
  s--;
  t--;
  auto hoge = dc.max_flow(s, t);
  cout << hoge << endl;

  vector<int> ans;
  vector<vector<int>> A(500, vector<int> (500, 0));
  dc.output(A);
  for(int i = 0; i < 500; i++) {
    for(int j = 0; j < 500; j++) {
      if(A[i][j] == 1 and A[j][i] == 1) {
        A[i][j] = 0;
        A[j][i] = 0;
      }
    }
  }
  
  for(int i = 0; i < 500; i++) {
    for(int j = 0; j < 500; j++) {
      if(A[i][j] == 1) {
        if(st.find({i, j}) == st.end()) ans.push_back(mp[make_pair(j, i)]);
      }
    }
  }

  cout << ans.size() << endl;
  for(auto val : ans) cout << val << endl;
  return 0;
}