1829F.md (1967B)
1 Source: https://codeforces.com/problemset/problem/1829/F 2 3 F. Forever Winter 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A snowflake graph is generated from two integers $x$ and $y$, both greater than $1$, as follows: 22 23 * Start with one central vertex. 24 * Connect $x$ new vertices to this central vertex. 25 * Connect $y$ new vertices to each of these $x$ vertices. 26 27 For example, below is a snowflake graph for $x=5$ and $y=3$.  28 29 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. 30 31 Given a snowflake graph, determine the values of $x$ and $y$. 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. 36 37 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. 38 39 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. 40 41 It is guaranteed that this graph is a snowflake graph for some integers $x$ and $y$ both greater than $1$. 42 43 Output 44 45 For each test case, on a separate line output the values of $x$ and $y$, in that order, separated by a space. 46 47 Example 48 49 Input 50 51 ``` 52 3 53 54 21 20 55 56 21 20 57 58 5 20 59 60 13 20 61 62 1 3 63 64 11 3 65 66 10 3 67 68 4 8 69 70 19 8 71 72 14 8 73 74 9 7 75 76 12 7 77 78 17 7 79 80 18 6 81 82 16 6 83 84 2 6 85 86 6 15 87 88 7 15 89 90 8 15 91 92 20 15 93 94 3 15 95 96 7 6 97 98 1 2 99 100 1 3 101 102 2 4 103 104 2 5 105 106 3 6 107 108 3 7 109 110 9 8 111 112 9 3 113 114 3 6 115 116 6 2 117 118 2 1 119 120 5 2 121 122 2 7 123 124 4 3 125 126 3 8 127 ``` 128 129 Output 130 131 ``` 132 5 3 133 2 2 134 2 3 135 ``` 136 137 Note 138 139 The first test case is pictured in the statement. Note that the output 3 5 is incorrect, since $x$ should be output before $y$.