codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.  ![](https://espresso.codeforces.com/9f2183c62c4c713927bb18746d1f5455da90f612.png)
     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$.