ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Personal Contest 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Routing

Time limit: 1.0 second
Memory limit: 64 MB
There is a TCP/IP net of several computers. It means that:
  1. Each computer has one or more net interfaces.
  2. Each interface is identified by its IP-address and a subnet mask — these are two four-byte numbers with a point after each byte. A subnet mask has a binary representation as follows: there are k 1-bits, then — m 0-bits, k+m=8*4=32 (e.g., — is an IP-address and — is a subnet mask).
  3. Two computers belong to the same subnet, if and only if (IP1 AND NetMask1) = (IP2 AND NetMask2), where IPi and NetMaski — are an IP-address and subnet mask of i-th computer, AND — is bitwise.
  4. A packet is transmitted between two computers of one subnet directly.
  5. If two computers belong to different subnets, a packet is to be transmitted via some other computers. The packet can pass from one subnet to another only on computer that has both subnets interfaces.
Your task is to find the shortest way of a packet between two given computers.


The first line contains a number N — an amount of computers in the net, then go N sections, describing interfaces of each computer. There is a number K in the first line of a section — that is an amount of interfaces of the computer, then go K lines — descriptions of the interfaces, i.e. its IP-address and a subnet mask. The last line of an input contains two integers — the numbers of the computers that you are to find a way between them.
You may assume that 2 ≤ N ≤ 90 and K ≤ 5.


The word “Yes” if the route exists, then in the next line the computer numbers passed by the packet, separated with a space. The word “No” otherwise.


1 6
1 3 5 6
Problem Author: Evgeny Kobzev
Problem Source: Ural State Univerisity Personal Contest Online February'2001 Students Session
To submit the solution for this problem go to the Problem set: 1072. Routing