Имеется сеть из нескольких компьютеров, с настроенной по правилам TCP/IP маршрутизацией. Это означает,
что:
- Каждый компьютер имеет 1 или более сетевых интерфейсов;
- Каждый интерфейс идентифицируется IP-адресом и маской подсети — это два 4-х байтных числа,
разделённые точками через каждый байт, причём в двоичном представлении маска подсети выглядит следующим образом: сначала идёт k единиц, потом m нулей, k + m = 8*4 = 32. (Например,
212.220.35.77 — IP-адрес, 255.255.255.128 — маска).
- 2 компьютера относятся к одной подсети, если (IP1 AND NetMask1) = (IP2 AND NetMask2), где IPi и
NetMaski — IP-адрес и маска i-го компьютера, AND — побитовое умножение.
- Пакет между компьютерами, находящими в одной подсети передаётся непосредственно.
- Пакет между компьютерами, находящимися в 2-х разных подсетях, проходит через компьютеры, имеющие интерфейсы, подключенные к нескольким подсетям, причём при переходе из подсети в подсеть компьютер, на котором осуществляется этот переход, должен иметь интерфейсы, относящиеся к обеим подсетям.
Задача состоит в том, чтобы найти кратчайший путь пакета между двумя указанными компьютерами.
Исходные данные
В первой строке стоит число N — количество компьютеров в сети, далее идёт N секций, описывающих интерфейсы каждого компьютера. В первой строке секции стоит число K — количество интерфейсов этого компьютера, затем следуют K строк с описанием интерфейсов в виде пар IP-адресов и масок. В последней строке стоят номера двух компьютеров, между которыми надо найти путь.
Известно, что 2 ≤ N ≤ 90 и K ≤ 5.
Результат
Если путь существует, выведите «Yes» и в следующей строке через пробел номера компьютеров, через которые проходит путь. Если такого пути не существует, выведите «No».
Пример
исходные данные | результат |
---|
6
2
10.0.0.1 255.0.0.0
192.168.0.1 255.255.255.0
1
10.0.0.2 255.0.0.0
3
192.168.0.2 255.255.255.0
212.220.31.1 255.255.255.0
212.220.35.1 255.255.255.0
1
212.220.31.2 255.255.255.0
2
212.220.35.2 255.255.255.0
195.38.54.65 255.255.255.224
1
195.38.54.94 255.255.255.224
1 6
| Yes
1 3 5 6
|
Автор задачи: Евгений Кобзев
Источник задачи: Ural State Univerisity Personal Contest Online February'2001 Students Session