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. [Image] (1) — bus, (2) — ring, (3) — star 

You'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. 


-----Input-----

The first line contains two space-separated integers n and m (4 ≤ n ≤ 10^5; 3 ≤ m ≤ 10^5) — the number of nodes and edges in the graph, correspondingly. Next m lines contain the description of the graph's edges. The i-th line contains a space-separated pair of integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ n) — the numbers of nodes that are connected by the i-the edge.

It is guaranteed that the given graph is connected. There is at most one edge between any two nodes. No edge connects a node with itself.


-----Output-----

In a single line print the network topology name of the given graph. If the answer is the bus, print "bus topology" (without the quotes), if the answer is the ring, print "ring topology" (without the quotes), if the answer is the star, print "star topology" (without the quotes). If no answer fits, print "unknown topology" (without the quotes).


-----Examples-----
Input
4 3
1 2
2 3
3 4

Output
bus topology

Input
4 4
1 2
2 3
3 4
4 1

Output
ring topology

Input
4 3
1 2
1 3
1 4

Output
star topology

Input
4 4
1 2
2 3
3 1
1 4

Output
unknown topology

Difficulty: interview

Starter code:

Solutions:
import re
import itertools
from collections import Counter, deque

class Task:
    n, m = 0, 0
    graph = []
    answer = ""
	
    def getData(self):
        self.n, self.m = [int(x) for x in input().split(' ')]
        for i in range(0, self.m):
            self.graph += [[int(x) for x in input().split(' ')]]

        #inFile = open('input.txt', 'r')
        #inFile.readline().rstrip()
        #self.childs = inFile.readline().rstrip()

    def solve(self):
        graph = self.graph
        vertexDegrees = [0] * (self.n + 1)
        for edge in graph:
            vertexDegrees[edge[0]] += 1
            vertexDegrees[edge[1]] += 1
        vertexDegrees = vertexDegrees[1:]
        if vertexDegrees.count(2) == len(vertexDegrees):
            self.answer = 'ring topology'
            return
        if vertexDegrees.count(1) == 2 and vertexDegrees.count(2) == \
                len(vertexDegrees) - 2:
            self.answer = 'bus topology'
            return
        if vertexDegrees.count(1) == len(vertexDegrees) - 1:
            self.answer = 'star topology'
            return
        self.answer = 'unknown topology'

    def printAnswer(self):
        print(re.sub(r'[\[\],]', '', str(self.answer)))
        #print(self.answer[:6])
        #outFile = open('output.txt', 'w')
        #outFile.write(self.answer)

task = Task()
task.getData()
task.solve()
task.printAnswer()



bt="bus topology"
st="star topology"
rt="ring topology"
ut="unknown topology"
def main():
    n,m=list(map(int,input().split()))
    S=[ 0 for j in range(n)];
    for _ in range(m):
        x,y=list(map(int,input().split()))
        S[x-1]+=1
        S[y-1]+=1
    if S.count(2)==len(S):
        print (rt)
        return
    elif S.count(2)==len(S)-2 and S.count(1)==2:
        print(bt)
        return
    elif (S.count(n-1)==1 and S.count(1)==len(S)-1):
        print(st)
        return
    else:
        print(ut)
        return
main()    


R = lambda: map(int, input().split())
n, m = R()
c = [0] * n
for i in range(m):
  x, y = R()
  c[x - 1] += 1
  c[y - 1] += 1
c1 = c2 = 0
for i in range(n):
  if c[i] == 1:
    c1 += 1
  elif c[i] == 2:
    c2 += 1
if c2 == n:
  print("ring topology")
elif c1 == 2 and c2 == n - 2:
  print("bus topology")
elif c1 == n - 1:
  print("star topology")
else:
  print("unknown topology")

n, m = map(int, input().split())
p = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    p[a] += 1
    p[b] += 1

ans = 'unknown topology'
if n == m:
    if p.count(2) == n: ans = 'ring topology'
elif n == m + 1:
    if n - 1 in p: ans = 'star topology'
    elif p.count(1) == 2 and p.count(2) == n - 2: ans = 'bus topology'
print(ans)

n,m=list(map(int,input().split()))
l=[0]*n
d=l[:]
for _ in range(m):
    a,b=list(map(int,input().split()))
    l[a-1]+=1
    l[b-1]+=1
for i in l:
    d[i]+=1
if(d[1]==2 and d[2]==n-2):
    print('bus topology')
elif(d[2]==n):
    print('ring topology')
elif(d[1]==n-1 and d[n-1]==1):
    print('star topology')
else:
    print('unknown topology')


n, m = (int(x) for x in input().split())
cnt = [0] * n
for i in range(m):
	u, v = (int(x) for x in input().split())
	cnt[u - 1] += 1
	cnt[v - 1] += 1
if cnt.count(1) == n - 1:
	print('star topology')
elif cnt.count(2) == n:
	print('ring topology')
elif cnt.count(1) == 2 and cnt.count(2) == n - 2:
	print('bus topology')
else:
	print('unknown topology')


# 292B

__author__ = 'artyom'

read = lambda: map(int, input().split())
n, m = read()
graph = [set() for _ in range(1 + n)]
degrees = [0] * (n + 1)
for __ in range(m):
  u, v = read()
  graph[u].add(v)
  graph[v].add(u)
  degrees[u] += 1
  degrees[v] += 1


def dfs(start):
  stack = [(start, None)]
  visited = [0] * (n + 1)
  while stack:
    v, parent = stack.pop()
    if degrees[v] > 2:
      return 'star' if all([degrees[u] == 1 for u in graph[v]]) else 'unknown'
    for u in graph[v]:
      if u != parent:
        if visited[u]:
          return 'ring' if u == start else 'unknown'
        stack.append((u, v))
    visited[v] = 1
  return 'bus'


print(dfs(1) + ' topology')

n, m = [int(k) for k in input().split()]
ans = 'bus topology'
dict = {}
count = 0
t = 0
if m >= n-1:
    for i in range(m):
        first, second = [int(k) for k in input().split()]
        if first not in dict:
            dict[first] = set()
            dict[first].add(second)
        else:
            if len(dict[first]) == 1:
                count += 1
            else: t += 1
            dict[first].add(second)
        if second not in dict:
            dict[second] = set()
            dict[second].add(first)
        else:
            if len(dict[second]) == 1:
                count += 1
            else: t += 1
            dict[second].add(first)
if count == n-2 and m == n-1:
    print('bus topology')
elif count == 1:
    print('star topology')
elif count == n and t == 0:
    print('ring topology')
else:
    print('unknown topology')

n, m = [int(k) for k in input().split()]
ans = 'bus topology'
dict = {}
count = 0
t = 0
if m >= n-1:
    for i in range(m):
        first, second = [int(k) for k in input().split()]
        if first not in dict:
            dict[first] = set()
            dict[first].add(second)
        else:
            if len(dict[first]) == 1:
                count += 1
            else: t += 1
            dict[first].add(second)
        if second not in dict:
            dict[second] = set()
            dict[second].add(first)
        else:
            if len(dict[second]) == 1:
                count += 1
            else: t += 1
            dict[second].add(first)
if count == n-2 and m == n-1:
    print('bus topology')
elif count == 1:
    print('star topology')
elif count == n and t == 0:
    print('ring topology')
else:
    print('unknown topology')


x,y = 0,0
countZero = 0
countOne = 0

n,m = [int(i) for i in input().split()]
a = [0]*n


for i in range(m):
    x,y = [int(i) for i in input().split()]
    a[y-1]+=1
    a[x-1]+=1

for i in a:
        if i==1:
            countZero+=1
        elif i>1:
            countOne+=1

if n==m:
    if countZero==0 and countOne==n:
        print('ring topology')
    else:
        print('unknown topology')
elif n-m==1:
    if countZero==2 and countOne==n-2:
        print('bus topology')
    elif countZero==n-1 and countOne==1:
        print('star topology')
    else:
        print('unknown topology')
else:
    print('unknown topology')




import sys
import math
n,m=list(map(int,input().split()))

degree=[0]*(n+1)

for _ in range(0,int(m)):
    a,b=list(map(int,input().split()))
    degree[a]=degree[a]+1
    degree[b]=degree[b]+1


if degree.count(1)==2 and degree.count(2)==n-2:
    print('bus topology')
elif degree.count(2)==n:
    print('ring topology')
elif degree.count(1)==n-1 and degree.count(n-1)==1:
    print('star topology')
else:
    print('unknown topology')


n,m=input().split()
n=int(n);m=int(m)
a=[0]*n
for i in range(0,m):
	x,y=input().split()
	x=int(x);y=int(y)
	a[x-1]+=1;a[y-1]+=1
r="unknown"
s=set(a)
if s=={2}:
	r="ring"
if s=={1,2}:
	r="bus"
if s=={1,m}:
	r="star"
print(r,"topology")

def solve():
    n, m = list(map(int, input().split()))
    if n not in (m, m + 1):
        return 3
    l = [0] * (n + 1)
    for _ in range(m):
        x, y = list(map(int, input().split()))
        l[x] += 1
        l[y] += 1
    c2 = l.count(2)
    if m == n == c2:
        return 1
    if m == n - 1:
        c1 = l.count(1)
        if c1 == 2 and c2 == n - 2:
            return 0
        if c1 == m and m in l:
            return 2
    return 3


def main():
    print(("bus", "ring", "star", "unknown")[solve()], "topology")


def __starting_point():
    main()

__starting_point()

3

n, m = [int(x) for x in input().split()]
degree = {0:0, 1:0, 2:0, n - 1:0}
visited = [0] * n
adjlist = [[] for x in range(n)]
for i in range(m):
	x, y = [int(x) for x in input().split()]
	x -= 1
	y -= 1
	adjlist[x].append(y) 
	adjlist[y].append(x)

for i in range(n):
	cur_degree = len(adjlist[i])
	if cur_degree not in degree:
		degree[cur_degree] = 1
	else:
		degree[cur_degree] += 1

degree_other = False

for val in list(degree.keys()):
	if val != 1 and val != 2 and val != n - 1 and val != 0:
		degree_other = True	

if degree_other == True:
	print("unknown topology")
elif degree[1] == n - 1 and degree[n - 1] == 1:
	print("star topology")
elif degree[1] == 2 and degree[2] == n - 2:
	print("bus topology")
elif degree[2] == n:
	print("ring topology")
else:
	print("unknown topology")


n,m=list(map(int,input().split()))

l=[0]*n

d=l[:]

for _ in range(m):

    a,b=list(map(int,input().split()))

    l[a-1]+=1

    l[b-1]+=1

for i in l:

    d[i]+=1

if(d[1]==2 and d[2]==n-2):

    print('bus topology')

elif(d[2]==n):

    print('ring topology')

elif(d[1]==n-1 and d[n-1]==1):

    print('star topology')

else:

    print('unknown topology')





# Made By Mostafa_Khaled


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

n, m = mints()
e = [[] for i in range(n+1)]

def isstar():
	c = None
	for i in range(1, n+1):
		if len(e[i]) > 1:
			if c != None:
				return False
			c = i
	if c == None:
		return False
	#for i in range(1,n+1)
	#	if i != c and e[i][0] != i:
	return len(e[c]) == n-1

def isbus():
	c = None
	for i in range(1, n+1):
		if len(e[i]) == 1:
			c = i
	if c == None:
		return False
	cnt = 2
	p = c
	c = e[c][0]
	while len(e[c]) == 2:
		if e[c][0] == p:
			p = c
			c = e[c][1]
		else:
			p = c
			c = e[c][0]
	return len(e[c]) == 1

def isring():
	p = 1
	if len(e[1]) != 2:
		return False
	c = e[1][0]
	while len(e[c]) == 2 and c != 1:
		if e[c][0] == p:
			p = c
			c = e[c][1]
		else:
			p = c
			c = e[c][0]
	return c == 1

for i in range(m):
	a, b = mints()
	e[a].append(b)
	e[b].append(a)
if isstar():
	print("star topology")
elif isbus():
	print("bus topology")
elif isring():
	print("ring topology")
else:
	print("unknown topology")


def main():
    n, m = list(map(int, input().split()))
    types = ['bus', 'ring', 'star', 'unknown']

    occ = [0] * n
    for i in range(m):
        a, b = list(map(int, input().split()))
        occ[a-1] += 1
        occ[b-1] += 1

    cnt = [0] * 3
    for v in occ:
        cnt[min(2, v-1)] += 1

    if cnt == [2, n - 2, 0]:
        res = types[0]
    elif cnt == [0, n, 0]:
        res = types[1]
    elif cnt == [n - 1, 0, 1]:
        res = types[2]
    else:
        res = types[3]

    print(res, 'topology')
        

def __starting_point():
    main()

__starting_point()

from array import array
from collections import Counter


n, m = list(map(int, input().split()))

a = array('L')

a.extend((0 for i in range(n)))

for i in range(m):
	x, y = list(map(int, input().split()))
	a[x-1] += 1
	a[y-1] += 1

ca = array('L')
ca.extend((0 for i in range(max(a)+1)))

for i in a:
	ca[i] += 1

def c(i):
	if i >= len(ca) or i < 0:
		return 0
	else:
		return ca[i]
		

if c(1) == 2 and c(2) == n-2:
	print("bus topology")
elif c(2) == n:
	print("ring topology")
elif c(1) == n-1 and c(n-1) == 1:
	print("star topology")
else:
	print("unknown topology")


n, m = list(map(int, input().split()))

vs = [0 for i in range(n)]

for i in range(m):
    x, y = list(map(int, input().split()))
    vs[x - 1] = vs[x - 1] + 1
    vs[y - 1] = vs[y - 1] + 1

if max(vs) == m and n == m + 1:
    print('star topology')
else:
    ones = sum([1 if x == 1 else 0 for x in vs])
    if n == m + 1 and ones == 2:
        print('bus topology')
    else:
        doubles = sum([1 if x == 2 else 0 for x in vs])
        if n == m and doubles == n:
            print('ring topology')
        else:
            print('unknown topology')


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n,m=f()
l=[0]*n
for _ in range(m):
    a,b=f()
    l[a-1]+=1
    l[b-1]+=1
l.sort()
if l[0]==1 and l[1]==1 and all(i==2 for i in l[2:]):
    print('bus topology')
elif all(i==2 for i in l):
    print('ring topology')
elif all(i==1 for i in l[:n-1]) and l[-1]==n-1:
    print('star topology')
else:
    print('unknown topology')

from functools import reduce
def add(a,b):
	return a+b
n,m = [int(x) for x in input().split()]
neigh = [[] for x in range(n)]
for i in range(m):
	x,y = [int(a) for a in input().split()]
	neigh[x-1].append(y)
	neigh[y-1].append(x)
oneneigh, twoneigh, nneigh = 0,0,0
for i in neigh:
	if len(i) == 1:
		oneneigh += 1
	elif len(i) == 2:
		twoneigh += 1
	else:
		nneigh += 1
if twoneigh == n:
	print('ring topology')
elif oneneigh == 2 and twoneigh == n-2:
	print('bus topology')
elif nneigh == 1 and oneneigh == m:
	print('star topology')
else:
	print('unknown topology')

def bus_topology(neigh):
	#check if exactly two nodes have 1 neighbor
	#check if all other nodes have 2 neighbors
	single_neighbors = 0
	for i in range(1, len(neigh)):
		if len(neigh[i]) == 1:
			single_neighbors += 1
		elif len(neigh[i]) > 2:
			return False
	
	if single_neighbors == 2:
		return True
	else:
		return False

def ring_topology(neigh):
	#check if all nodes have exactly two neighbors
	for i in range(1, len(neigh)):
		if len(neigh[i]) > 2:
			return False
	return True

def star_topology(neigh, n):
	#check if one node has n-1 neighbors
	#check if all nodes have 1 neighbor 
	centernode = 0
	for i in range(1, len(neigh)):
		if len(neigh[i]) == n-1:
			centernode += 1
		elif len(neigh[i]) != 1:
			return False

	if centernode == 1:
		return True
	else:
		return False

n,m = [int(x) for x in input().split()]
#nodes, edges
neighbors = [[] for x in range(n+1)]

for i in range(m):
	u,v = (int(x) for x in input().split())
	neighbors[u].append(v)
	neighbors[v].append(u)

#for i in range(len(neighbors)):
#	print(i, neighbors[i])

if bus_topology(neighbors):
	print("bus topology")
elif ring_topology(neighbors):
	print("ring topology")
elif star_topology(neighbors,n):
	print("star topology")
else:
	print("unknown topology")

from collections import Counter

n, m = map(int, input().split())

g = [[] for _ in range(n)]

for i in range(m):
    x, y = map(int, input().split())
    g[x - 1].append(y - 1)
    g[y - 1].append(x - 1)

bus = ([2] * (n - 2)) + ([1] * 2)
star = [1] * (n - 1) + [n - 1]

lns = [len(lst) for lst in g]
if lns == [2] * n:
    print("ring topology")
elif Counter(lns) == Counter(bus):
    print("bus topology")
elif Counter(lns) == Counter(star):
    print("star topology")
else:
    print("unknown topology")

n, m = map(int, input().split())
a = []
for i in range(0, n+1):
    a.append([])
for i in range(m):
    i, j = map(int, input().split())
    a[i].append(j)
    a[j].append(i)
c = 0
d = 0
f = 0
for el in a:
    if(len(el)==1):
        c+=1 
    elif(len(el)==2):
        d+=1 
    elif(len(el)==n-1):
        f+=1 
if(c==2 and d==n-2):
    print("bus topology")
elif(d==n):
    print("ring topology")
elif(f==1 and c==n-1):
    print("star topology")
else:
    print("unknown topology")

n,m = map(int,input().split())
a = []
for h in range(0,n+1):
    a.append([])
for i in range(m):
    k,j = map(int,input().split())
    a[k].append(j)
    a[j].append(k)
d2 = 0
d1 = 0
d3 = 0
for u in a:
    if len(u) == 1 :
        d1+=1
    if len(u) == 2 :
        d2+=1
    if len(u) == n-1:
        d3+=1
if d1 == 2 and d2 == n-2:
    print("bus topology")
elif d3 == 1 and d1 == n-1:
    print("star topology")
elif d2 == n:
    print("ring topology")
else:
    print("unknown topology")