Reverse Roads

Time limit5sMemory limit512 MB

Summary

Given a directed graph with unit capacities, reverse some edges to maximize the number of edge-disjoint S to T paths, and report the reversed edges.

Level: Medium7 of 10
Topics: Graph, Shortest path, Greedy, Implementation
Solved: No attempts yet

Problem

In ICP city there is a delivery company whose trucks run from crossing S to crossing T. The president of the company is upset because every road in the city is one-way and severely congested. So he plans to increase the maximum flow (edge disjoint paths) from crossing S to crossing T by reversing the traffic direction on some of the roads.

Write a program that computes the maximized flow from S to T after reversing some roads, together with the list of reversed roads.

Input

The first line of a data set contains two integers N (2≤N≤300) and M (0≤M≤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 the one-way roads of the city. The i-th line (1-based) contains two integers Xi and Yi (1≤Xi,Yi≤N, Xi≠Yi). Xi is the ID number (1-based) of the starting point of the i-th road and Yi is that of its terminal point. The last line contains two integers S and T (1≤S,T≤N, S≠T, 1-based).

The capacity of each road is 1. You can assume that i≠j implies either Xi≠Xj or Yi≠Yj, and either Xi≠Yj or Xj≠Yi.

Output

In the first line, print the maximized flow obtained by reversing some roads. In the second line, print the number R of 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 multiple answers give the same flow, you may print any of them.

Examples3

Example 1
Input
```
2 1
2 1
2 1
```
Expected output
```
1
0
```
Example 2
Input
```
2 1
1 2
2 1
```
Expected output
```
1
1
1
```
Example 3
Input
```
3 3
3 2
1 2
3 1
1 3
```
Expected output
```
2
2
1
3
```