Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tarnacop.in, tarnacop.out | Sursă | Algoritmiada 2012, Runda Finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 1 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tarnacop
Due to excessive mining, the mine shafts near Targu Mures have been flooded by an underground river. The mine shafts can be considered as a graph with N vertices (N rooms) and M edges (M corridors between the rooms). The room where the accident occurred (where the underground river enters the mine shafts) is known, and we shall refer to it as room S. Giugudel has come to give aid to the mine workers, bringing along his magic pickaxe. Using it, he managed to dig a leak for the underground river, leak which is located in room D. Giugudel knows for each corridor the capacity (number of cubic meters of water that can pass through it during one second), and the actual quantity of water that passes thorough the corridor. Obviously, this quantity is less or equal to the capacity. Giugudel knows the number of cubic meters of water that pass in each second through the leak in room D, and would be interested in knowing for each corridor, if its capacity would be decreased by one, if the water quantity that is flushed through room D would also decrease.
Input
The input file tarnacop.in will contain on the first line four integers N,M,S,D, with their meaning described above. Each of the following M lines will contain a quadruplet of the type X,Y,C,I, describing a corridor between rooms X and Y, of C capacity, through which pass I m3 of water every second.
Output
The output file tarnacop.out will contain on its first line an integer number K, describing the number of edges with the property requested in the problem's statement. On each of the following K lines there will be a pair of ingeres X,Y describing the fact that the edge form X to Y has the requested property. The edges must be written in increasing X order, and in case of equal X-es, increasing Y order.
Restrictions
- 1 ≤ S, D ≤ N ≤ M ≤ 100 000
- S ≠ D
- 0 ≤ I ≤ C ≤ 5 000 000
- Water can flow through a corridor only in the direction given in the input (for an edge X,Y, water will always flow from X to Y)
- There won't be more than one edge between any two vertexes
- There won't be an edge from a vertex to itself
Example
| tarnacop.in | tarnacop.out |
|---|---|
| 4 4 1 4 1 2 1 1 2 3 1 1 3 4 1 1 2 4 2 0 | 1 1 2 |
