Forever Winter (Codeforces 1829F)
Tags: Math, dfs and similar

A snowflake graph is generated from two integers $$$x$$$ and $$$y$$$, both greater than $$$1$$$, as follows:   Start with one central vertex.  Connect $$$x$$$ new vertices to this central vertex.  Connect $$$y$$$ new vertices to each of these $$$x$$$ vertices.  For example, below is a snowflake graph for $$$x=5$$$ and $$$y=3$$$.  The snowflake graph above has a central vertex $$$15$$$, then $$$x=5$$$ vertices attached to it ($$$3$$$, $$$6$$$, $$$7$$$, $$$8$$$, and $$$20$$$), and then $$$y=3$$$ vertices attached to each of those.  Given a snowflake graph, determine the values of $$$x$$$ and $$$y$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 200$$$; $$$1 \leq m \leq \min\left(1000, \frac{n(n-1)}{2}\right)$$$) — the number of vertices and edges in the graph, respectively.The next $$$m$$$ lines each contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) — the numbers of vertices connected by an edge. The graph does not contain multiple edges and self-loops.It is guaranteed that this graph is a snowflake graph for some integers $$$x$$$ and $$$y$$$ both greater than $$$1$$$.

Output: For each test case, on a separate line output the values of $$$x$$$ and $$$y$$$, in that order, separated by a space.

Note: The first test case is pictured in the statement. Note that the output 3 5 is incorrect, since $$$x$$$ should be output before $$$y$$$.

Sample Inputs:
3
21 20
21 20
5 20
13 20
1 3
11 3
10 3
4 8
19 8
14 8
9 7
12 7
17 7
18 6
16 6
2 6
6 15
7 15
8 15
20 15
3 15
7 6
1 2
1 3
2 4
2 5
3 6
3 7
9 8
9 3
3 6
6 2
2 1
5 2
2 7
4 3
3 8

Sample Outputs:
5 3
2 2
2 3

Solution (Python):
import sys
import math
import bisect
import heapq
import itertools
from itertools import accumulate
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 1000000007

def get_ints():
    return map(int, sys.stdin.readline().strip().split())

def get_list():
    return list(map(int, sys.stdin.readline().strip().split()))

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

def get_int():
    return int(sys.stdin.readline().strip())

def get_list_strings():
    return list(map(str, sys.stdin.readline().strip().split()))

def solve():
    (n, m) = get_ints()
    graph = [0] * (n + 1)
    for _ in range(m):
        (x, y) = get_ints()
        graph[x] += 1
        graph[y] += 1
    g2 = Counter(graph[1:])
    c = 1
    d = 1
    for i in g2:
        if g2[i] == 1 and i != 1:
            c = i
        elif g2[i] > 1 and i != 1:
            d = i
    if c == 1:
        c = d
    return [c, d - 1]
if __name__ == '__main__':
    for i in range(get_int()):
        print(*solve())

Solution (Python):
import sys
inputs = sys.stdin.readline().rstrip().split(' ')
cases = int(inputs[0])
for case in range(cases):
    inputs = sys.stdin.readline().rstrip().split(' ')
    (n, m) = (int(inputs[0]), int(inputs[1]))
    connections = [0] * n
    for edge in range(m):
        inputs = sys.stdin.readline().rstrip().split(' ')
        (u, v) = (int(inputs[0]), int(inputs[1]))
        connections[u - 1] += 1
        connections[v - 1] += 1
    x = len(connections) - 1 - connections.count(1)
    y = connections.count(1) // x
    print(str(x) + ' ' + str(y))

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    graph = [0 for _ in range(n)]
    for _ in range(m):
        (a, b) = map(int, input().split())
        graph[a - 1] += 1
        graph[b - 1] += 1
    graph.sort()
    one = 0
    for i in range(n):
        if graph[i] != 1:
            break
        one += 1
    if graph[one + 1] == graph[one]:
        two = -1
        for i in range(one + 2, n):
            if graph[one] != graph[i]:
                two = graph[i]
                break
        if two == -1:
            two = graph[one]
    elif graph[one] == graph[one + 2]:
        two = graph[one + 1]
    else:
        two = graph[one]
    print(two, one // two)