喵~, 主人，欢迎来到我的解题小课堂！今天我们要看一道非常可爱的题目，叫做 'Forever Winter'，它和一种叫做 '雪花图' 的东西有关哦 ❄️。一听就很浪漫对不对？别担心，这道题就像冬天里的小猫一样，看起来冷酷，其实只要摸清了它的脾气，就非常温顺好解啦。让我们一起来看看吧，喵~

题目大意

题目给了我们一个特殊的图，它叫做『雪花图』。这个图是这么画出来的呢？

1. 首先，我们在中间放一个点，叫它『中心点』，喵。
2. 然后，从这个中心点连出来 x 条线，分别连接到 x 个新的点上。这些点就像是雪花的分叉，我们叫它们『星星点』好了。
3. 最后，再从每一个『星星点』上，连出来 y 条线，分别连接到 y 个新的点上。这些最外面的点，就像雪花的末梢，我们叫它们『叶子点』吧。

题目会给我们一个已经画好的雪花图（但是不会告诉我们哪个是中心点，哪些是星星点），我们的任务就是根据这个图的连接方式，找出 x 和 y 这两个数字是多少。

题目保证了给定的图一定是雪花图，而且 x 和 y 都大于 1 哦。

题解方法

要解决这个问题，关键在于观察每个点的『度』，喵！一个点的『度』，就是连接到这个点的边的数量，很简单吧？

我们来分析一下不同类型点的『度』有什么特征：

• 中心点: 它连接了 x 个星星点，所以它的度就是 x。整个图里只有一个中心点哦！
• 星星点: 每个星星点都连接着 1 个中心点和 y 个叶子点，所以它的度是 1 + y。图里一共有 x 个星星点。
• 叶子点: 每个叶子点只连接着 1 个星星点，所以它的度永远是 1。图里一共有 x * y 个叶子点。

这样一来，思路就清晰多啦！我们可以通过点的度来区分它们！

叶子点最容易找，它们的度都是 1。剩下的点（中心点和星星点）的度都大于 1。

那么，怎么区分中心点和星星点呢？这就要分两种情况讨论了，喵~

情况一：中心点和星星点的度不相等 (x ≠ 1 + y)

在这种情况下，中心点的度是 x，星星点的度是 1 + y。因为 x 和 1 + y 是两个不同的数，所以我们在图中会看到两种度大于 1 的点。

• 中心点只有一个，所以度为 x 的点只有一个。
• 星星点有 x 个，因为题目保证了 x > 1，所以度为 1 + y 的点有多个。

Bingo！这就是突破口！在所有度大于 1 的点中，那个只出现了一次的度，肯定不属于星星点。反过来说，那个出现了超过一次的度，一定是星星点的度！

所以，我们只需要统计一下所有点的度的数量。找到那个数量大于 1 且度也大于 1 的度 d，那么它必然是星星点的度，即 d = 1 + y。这样我们就能算出 y = d - 1。

算出了 y，x 怎么算呢？还记得叶子点吗？叶子点的总数是 x * y。我们只要数一数图中度为 1 的点的个数，再除以我们刚刚算出的 y，就能得到 x 啦！

情况二：中心点和星星点的度正好相等 (x = 1 + y)

这种情况就更有趣了，喵~ 如果中心点和星星点的度相等，那么所有非叶子点的度都是一样的，都等于 x。

• 中心点（1个）的度是 x。
• 星星点（x个）的度是 1+y，也等于 x。

所以，我们统计度的数量时，会发现只有一种大于 1 的度。设这个度为 d。 那么很明显，d 就是中心点的度，所以 x = d。 同时，d 也是星星点的度，所以 d = 1 + y，也就是 y = d - 1。 这样，x 和 y 也都找到啦！

总结一下我们的策略：数出图中每种度的点的个数。然后看看度大于 1 的有几种。如果只有一种，就是情况二；如果有两种，就是情况一。是不是很简单呀，喵？

题解

下面是具体的代码实现，我已经加上了详细的注释，方便主人理解哦~

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

void solve() {
    int n, m;
    std::cin >> n >> m;
    // 用一个 vector 来记录每个点的度，喵~
    std::vector<int> degree(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        degree[u]++;
        degree[v]++;
    }

    // 用一个 map 来统计每种度出现的次数
    // freq[d] = c 表示度为 d 的点有 c 个
    std::map<int, int> freq;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] > 0) { // 只统计图中存在的点
            freq[degree[i]]++;
        }
    }

    // 统计度大于1的种类数
    int non_leaf_degree_types = 0;
    for (auto const& [deg, count] : freq) {
        if (deg > 1) {
            non_leaf_degree_types++;
        }
    }

    if (non_leaf_degree_types == 2) {
        // 这是情况一: x != 1 + y
        // 我们要找到星星点的度，它的特征是：度 > 1 且 出现的次数 > 1
        int star_node_degree = 0;
        for (auto const& [deg, count] : freq) {
            if (count > 1 && deg > 1) {
                star_node_degree = deg;
                break;
            }
        }
        // 星星点的度是 1 + y
        int y = star_node_degree - 1;
        
        // 叶子点的数量是 freq[1]，也等于 x * y
        // 所以 x = 叶子点数量 / y
        int x = freq.at(1) / y;
        
        std::cout << x << " " << y << std::endl;

    } else { // non_leaf_degree_types == 1
        // 这是情况二: x = 1 + y
        // 此时所有非叶子点的度都相同，这个度就是 x
        // 我们可以直接找到那个唯一的、大于1的度
        // map的rbegin()指向键最大的元素，也就是度最大的那个
        int x = freq.rbegin()->first;
        int y = x - 1;
        std::cout << x << " " << y << std::endl;
    }
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

通过这道题，我们又学到了一些有用的知识呢，喵~

1. 图论基础 (Graph Theory Basics):

   • 顶点 (Vertex) 和 边 (Edge): 图的基本组成部分，就像拼图的碎片和连接处。
   • 度 (Degree): 一个顶点连接了多少条边。这是图论问题中一个非常非常重要的属性，很多问题的突破口都在于分析点的度！

2. 常用数据结构 (Data Structures):

   • std::vector: 一个动态数组，用来存每个点的度非常方便，可以通过下标 degree[i] 直接访问第 i 个点的度。
   • std::map: 一个键-值对容器，可以自动根据键排序。在这里我们用它来建立 度 -> 数量 的映射关系，能快速统计出每种度的点有多少个。

3. 解题思维 (Problem-Solving Strategy):

   • 观察与归纳: 首先要仔细观察题目给出的『雪花图』结构，归纳出不同类型顶点的性质。
   • 分类讨论 (Case Analysis): 将问题根据关键性质（这里是中心点和星星点的度是否相等）分解成几个更简单的小问题。这是我们解决复杂问题时非常有用的一个技巧，喵！

好啦，今天的解题小课堂就到这里啦！主人有没有觉得这道题其实很直白可爱呢？只要抓住了『度』这个关键点，问题就迎刃而解了。希望我的讲解对你有帮助哦！下次再见啦，喵~ 💖