CF292B Network Topology

This problem uses a simplified network topology model, please read the problem statement carefully and use it as a formal document as you develop the solution. Polycarpus continues working as a system administrator in a large corporation. The computer network of this corporation consists of $ n $ computers, some of them are connected by a cable. The computers are indexed by integers from $ 1 $ to $ n $ . It's known that any two computers connected by cable directly or through other computers Polycarpus decided to find out the network's topology. A network topology is the way of describing the network configuration, the scheme that shows the location and the connections of network devices. Polycarpus knows three main network topologies: bus, ring and star. A bus is the topology that represents a shared cable with all computers connected with it. In the ring topology the cable connects each computer only with two other ones. A star is the topology where all computers of a network are connected to the single central node. Let's represent each of these network topologies as a connected non-directed graph. A bus is a connected graph that is the only path, that is, the graph where all nodes are connected with two other ones except for some two nodes that are the beginning and the end of the path. A ring is a connected graph, where all nodes are connected with two other ones. A star is a connected graph, where a single central node is singled out and connected with all other nodes. For clarifications, see the picture. (1) — bus, (2) — ring, (3) — starYou've got a connected non-directed graph that characterizes the computer network in Polycarpus' corporation. Help him find out, which topology type the given network is. If that is impossible to do, say that the network's topology is unknown.

N/A

N/A