Дан ориентированный граф, состоящий из n вершин и m ребер, с выделенными вершинами s и t. При этом, в вершину s не входит ни одного ребра, а из вершины t не выходит ни одного ребра.
Изначально у каждого ребра была целая пропускная способность ci > 0. В сети с истоком s и стоком t был построен некоторый максимальный поток, и на ребре номер i записали fi — сколько единиц потока течет по этому ребру. Затем все пропускные способности ci и величины fi потока стерли, оставив лишь направление ребра и индикаторы gi: течет ли по ребру поток, т.е. 1, если fi > 0, и 0 иначе.
По графу и индикаторам gi определите, каково минимально возможное число насыщенных ребер в этой сети (ребро i является насыщенным, если fi = ci), и постройте соответствующую сеть c максимальным потоком в ней.
Поток в ориентированном графе задается величинами потока fi на каждом ребре такими, что выполняются условия:
- для каждой вершины, кроме истока и стока, сумма потока на входящих и выходящих из нее ребрах одинакова
- для каждого ребра 0 ≤ fi ≤ ci
Максимальный поток — такой поток, в котором разность между суммой величин потоков на ребрах, выходящих из истока, и суммой величин потоков на ребрах, входящих в исток (таких в этой задаче нет), максимальна.
Выходные данные
В первой строке выведите целое число k — минимальное число ребер, которые должны быть насыщены в максимальном потоке.
В каждой из следующих m строк выведите два целых числа fi, ci (1 ≤ ci ≤ 109, 0 ≤ fi ≤ ci) — поток по ребру номер i и пропускную способность ребра номер i. Эти данные должны задавать корректный максимальный поток в сети с такими пропускными способностями, ровно для k ребер должно выполняться fi = ci, а также fi > 0 должно выполняться тогда и только тогда, когда во входных данных для gi = 1.
Если возможных ответов несколько, выведите любой из них.
Примечание
Иллюстрация к примеру из условия. Темным обозначены насыщенные ребра, пунктиром — ребро, по которому не идет поток (gi = 0). Число на ребре — номер данного ребра в списке. 
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 1 5
1 2 1
2 3 1
3 5 1
1 4 1
4 3 0
4 5 1
|
2
3 3
3 8
3 4
4 4
0 5
4 9
|