Банк заданий
ЕГЭ по информатике

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 723 в вершину с номером 336. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 701 в вершину с номером 676. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 358 в вершину с номером 70. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 985 в вершину с номером 164. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 651 в вершину с номером 803. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 117 в вершину с номером 648. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 851 в вершину с номером 496. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 867 в вершину с номером 608. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе целую часть длины наибольшего по сумме весов пути из вершины с номером 623 в вершину с номером 2. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и наибольшего по сумме весов пути из вершины 6 в вершину с номером 12 верным ответом будет 14. Возможные маршруты: 6 → 7 → 100 → 12, длина $7 + 2 + 1 = 10$; 6 → 1 → 7 → 100 → 12, длина $1 + 5{,}5 + 2 + 1 = 9{,}5$; 6 → 1 → 100 → 12, длина $1 + 12 + 1 = 14$; 6 → 1 → 4 → 100 → 12, длина $1 + 2{,}5 + 8 + 1 = 12{,}5$. Целая часть наибольшей длины — 14.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 725 в вершину с номером 798. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 682 в вершину с номером 339. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 792 в вершину с номером 317. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 158 в вершину с номером 973. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 129 в вершину с номером 131. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 464 в вершину с номером 814. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 377 в вершину с номером 183. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 651 в вершину с номером 625. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 868 в вершину с номером 18. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 35 в вершину с номером 66. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 825 в вершину с номером 301. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 641 в вершину с номером 990. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 166 в вершину с номером 844. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ — номера вершин графа. Ребро ведёт из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе количество различных путей из вершины с номером 146 в вершину с номером 704. Существование хотя бы одного такого пути гарантируется. Под путём понимается последовательность вершин, в которой каждая следующая вершина соединена с предыдущей направленным ребром. Каждое ребро может использоваться не более одного раза. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12

6 7

6 1

1 7

7 100

4 100

1 100

1 4

Для приведённого примера и количества различных путей из вершины 1 в вершину с номером 100 верным ответом будет 3: 1 → 100; 1 → 7 → 100; 1 → 4 → 100.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе минимально возможное количество рёбер на пути из вершины с номером 628 в вершину с номером 612. Существование хотя бы одного такого пути гарантируется. Количество рёбер — это число переходов между соседними вершинами пути; веса рёбер при подсчёте не учитываются. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и минимально возможного количества рёбер на пути из вершины 6 в вершину с номером 12 верным ответом будет 3. Маршруты 6 → 7 → 100 → 12 и 6 → 1 → 100 → 12 содержат по 3 ребра; 6 → 1 → 7 → 100 → 12 и 6 → 1 → 4 → 100 → 12 — по 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа $L$ и $M$ и одно положительное вещественное число $W$. $L$ и $M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.

Найдите и запишите в ответе минимально возможное количество рёбер на пути из вершины с номером 281 в вершину с номером 628. Существование хотя бы одного такого пути гарантируется. Количество рёбер — это число переходов между соседними вершинами пути; веса рёбер при подсчёте не учитываются. Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000$, $M ≤ 1000$, $W ≤ 10000$. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле:

100 12 1.0

6 7 7.0

6 1 1.0

1 7 5.5

7 100 2.0

4 100 8.0

1 100 12.0

1 4 2.5

Для приведённого примера и минимально возможного количества рёбер на пути из вершины 6 в вершину с номером 12 верным ответом будет 3. Маршруты 6 → 7 → 100 → 12 и 6 → 1 → 100 → 12 содержат по 3 ребра; 6 → 1 → 7 → 100 → 12 и 6 → 1 → 4 → 100 → 12 — по 4.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.