도로 뒤집기

시간 제한5초메모리 제한512 MB

요약

단위 용량 방향 그래프에서 일부 간선의 방향을 뒤집어 S에서 T로 가는 간선 서로소 경로 수를 최대로 만들고, 뒤집은 간선 목록을 출력한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

ICP 시에는 교차로 S에서 교차로 T로 트럭을 운행하는 택배 회사가 있다. 시의 모든 도로가 일방통행이고 혼잡이 심해 회사 사장은 고민에 빠졌다. 그래서 일부 도로의 통행 방향을 뒤집어 교차로 S에서 교차로 T로 가는 최대 흐름(서로 간선을 공유하지 않는 경로)을 늘리려 한다.

일부 도로를 뒤집어 S에서 T로 가는 흐름을 최대로 만들었을 때의 값과 뒤집은 도로의 목록을 구하는 프로그램을 작성하시오.

입력

데이터 세트의 첫 줄에는 두 정수 N(2≤N≤300)과 M(0≤M≤min(1 000, N(N−1)⁄2))이 주어진다. N은 시의 교차로 수이고 M은 도로 수이다.

다음 M개 줄은 시의 일방통행 도로를 나타낸다. i번째 줄(1부터 시작)에는 두 정수 Xi와 Yi(1≤Xi,Yi≤N, Xi≠Yi)가 주어진다. Xi는 i번째 도로의 시점 ID(1부터 시작)이고 Yi는 종점 ID이다. 마지막 줄에는 두 정수 S와 T(1≤S,T≤N, S≠T, 1부터 시작)가 주어진다.

각 도로의 용량은 1이다. i≠j이면 Xi≠Xj 또는 Yi≠Yj이고, Xi≠Yj 또는 Xj≠Yi라고 가정할 수 있다.

출력

첫 줄에는 일부 도로를 뒤집어 얻은 최대 흐름을 출력한다. 둘째 줄에는 뒤집은 도로의 수 R을 출력한다. 다음 R개 줄에는 뒤집은 도로의 ID(1부터 시작)를 출력한다. 같은 ID를 두 번 이상 출력하면 안 된다.

흐름이 같아지는 답이 여러 개라면 그중 아무거나 출력해도 된다.

예제3

예제 1
입력
```
2 1
2 1
2 1
```
예상 출력
```
1
0
```
예제 2
입력
```
2 1
1 2
2 1
```
예상 출력
```
1
1
1
```
예제 3
입력
```
3 3
3 2
1 2
3 1
1 3
```
예상 출력
```
2
2
1
3
```