Codeforces Round 871 (Div. 4) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

graphs

math

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Forever Winter

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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.

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.

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.

Example

Input

321 2021 205 2013 201 311 310 34 819 814 89 712 717 718 616 62 66 157 158 1520 153 157 61 21 32 42 53 63 79 89 33 66 22 15 22 74 33 8

Output

5 3 2 2 2 3

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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2024 10:39:16 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|