Problem C
Stealing Railways
You are the leader of the metal mob in Minsk. You know that the Soviet Union needs to ship a lot of soldiers from Siberia to the western front. However since the last $5$-year plan the railway network is oversized and you see the opportunity of stealing some railway and selling the metal on the highly overpriced black market. If you steal too much, enough soldiers may not be able to travel to the western front. That will raise suspicion and you are a person of high interest, so you might be departed to Gulag if that happens.
You have obtained a map of the railway network from an American agent. This was the easiest way of obtaining this information since if someone found out about you having a map of the entire Soviet Union you would definitely be deported to the Gulag. In exchange the agent needs to know a minimal cut in the graph after you have stolen some railway lines. This information would be very useful to the Americans and your loyalty is easily changed with an opportunity to earn a lot of money.
You have set up a plan which contains which railway lines to steal and in what order. However you stop before the maximum flow of soldiers in the railway network becomes lower than the given threshold, or when your plan is finished.
Input
The first line of the input contains four integers $N \ M \ C \ P$, where $N$ and $M$ represent the number of nodes and edges in the railway network, such that $2 \leq N \leq 100$ and $1 \leq M \leq \frac{N(N-1)}{2}$. The threshold of the flow of soldiers is represented by $C$. It is guaranteed that the max flow through the graph without any removed edges is at least as large as $C$. The number of railways in your plan is represented by $P$ such that $1 \leq P \leq M$.
Then follow $M$ lines, each representing an undirected edge. An edge is represented by three integers, $u_ i \ v_ i \ c_ i$, which means that the $i^\textrm {th}$ edge is between node $u_ i$ and $v_ i$ with the capacity $c_ i$, where $0 \leq u_ i < v_ i < N$ and $1 \leq c_ i \leq 100$. There are no two edges between the same pair of nodes.
The last $P$ lines describes the plan. Each line consists of one integer $m_ i$, the index of the railway line that you are about to steal next, which means that $0 \leq m_ i < M$.
No edge appears twice in the plan. Node $0$ represents Siberia and node $N-1$ represents the western front.
Output
The output starts with a line containing three integers $x \ f \ s$, where $x$ is the number of railway lines you managed to steal. Given the graph $G$ that is left when you have stolen the $x$ first railways in your plan, $f$ is the maximum flow and $s$ is the size of a minimal cut of $G$.
Following is a second line containing $s$ integers, which are the indexes of edges that form a minimal cut of $G$. Any minimal cut of $G$, with edges in any order, is considered correct.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 10 3 0 1 10 0 2 10 1 2 10 0 2 1 |
2 10 1 1 |