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:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }

const int INF = 1L << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy = { 0, 1, 0, -1 }, dx = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）

using namespace std;

struct Edge {
    const int to;         // 行き先のノードid
    int flow;             // 流量
    const int cap;        // 容量
    const int rev;        // 逆辺のノードid
    const bool is_rev;    // 逆辺かどうか
    Edge(int to, int flow, int cap, int rev, bool is_rev) : to(to), flow(flow), cap(cap), rev(rev), is_rev(is_rev) {
        assert(this->cap >= 0);
    }
};

// 最大流問題をO(F|E|)で解く
class FordFulkerson {
public:
    const unsigned int num_of_node = 0;   // ノード数
    map<int, vector<Edge>> G;       // グラフの隣接リスト表現

    FordFulkerson(unsigned int num_of_node) : num_of_node(num_of_node) {
    }

    // fromからtoへ向かう容量capの辺とその逆辺をグラフに追加する
    void add_edge(int from, int to, int cap) {
        this->G[from].emplace_back(Edge(to, 0, cap, (int)this->G[to].size(), false));          // 辺
        this->G[to].emplace_back(Edge(from, cap, cap, (int)this->G[from].size() - 1, true));     // 逆辺
    }

    // sからtへの最大流を求める O(F|E|)
    int max_flow(int s, int t) {
        int flow = 0;
        while (true) {
            vector<bool> used(this->num_of_node, false); // DFSですでに調べたかのフラグ
            int f = dfs(s, t, INT_MAX, used);
            if (f == 0) { return flow; }
            flow += f;
        }
    }

    // 水の流れたエッジを取得する
    set<pair<int, int>> get_used_edges() {
        set<pair<int, int>> used_edges;

        for (auto p : this->G) {
            int from = p.first;
            for (Edge edge : p.second) {
                int flow = edge.flow;
                bool is_rev = edge.is_rev;

                if (not is_rev and flow > 0) {
                    int to = edge.to;
                    used_edges.insert(make_pair(from , to));
                }
            }
        }
        return used_edges;
    }

private:
    // vからtへf流したときの流れた量
    int dfs(int from, int to, int f, vector<bool> &used) {
        if (from == to) { return f; }
        used[from] = true;
        for (Edge &e : G[from]) {
            int rest = e.cap - e.flow;
            if (!used[e.to] && rest > 0) {
                int d = dfs(e.to, to, min(f, rest), used);
                if (d > 0) {
                    e.flow += d;                 // 辺
                    G[e.to][e.rev].flow -= d;    // 逆辺
                    return d;
                }
            }
        }
        return 0;
    }

};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M, S, T;
    cin >> N >> M;
    FordFulkerson ff(N + 10);
    V<pair<int, int>> edges;
    FOR(i, 0, M) {
        int x, y;
        cin >> x >> y;
        edges.emplace_back(make_pair(x, y));
        ff.add_edge(x, y, 1);
        ff.add_edge(y, x, 1);

    }
    cin >> S >> T;

    int flow = ff.max_flow(S, T);

    vector<int> ans;
    auto used_edges = ff.get_used_edges();
    FOE(edge, used_edges) {
        int from = edge.first;
        int to = edge.second;

        FOR(i, 0, edges.size()) {
            int from2 = edges[i].first;
            int to2 = edges[i].second;

            if (from == to2 and to == from2) {
                ans.emplace_back(i + 1);
                break;
            }
        }
    }
    sort(ALL(ans));

    print(flow);
    print(ans.size());
    FOE(x, ans) {
        print(x);
    }

    return 0;
}