Forever Winter

标签：Forever Winter int graph vertices each test output

Forever Winter time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

A snowflake graph is generated from two integers x and y, both greater than 11, 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=5 and y=3=3.

The snowflake graph above has a central vertex 1515, then x=5=5 vertices attached to it (33, 66, 77, 88, and 2020), and then y=3=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≤t≤10001≤≤1000) — the number of test cases.

The first line of each test case contains two integers n and m (2≤n≤2002≤≤200; 1≤m≤min(1000,n(n−1)2)1≤≤min(1000,(−1)2)) — the number of vertices and edges in the graph, respectively.

The next m lines each contain two integers each u and v (1≤u,v≤n1≤,≤, u≠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 11.

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 Copy 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 output Copy

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.

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
string s;
int n,t,f[N],res,num,ans,m;
bool vis[N];
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        ans=0;
        map<int,int>a;
        for(int i=0;i<n;i++){
            cin>>f[i];
            a[f[i]]=1;
        }
        for(int i=0;i<=n;i++)//只需要找到一个所有的子节点都不是1的点就可以
            if(!a.count(i)){
                num=i;
                break;
            }
        int l=0,r=0;
        for(int i=0;i<n;i++){
            if(f[i]==num+1){
                if(l==0) l=i;
                r=i;
            }
        }

    }
    return 0;
}

 

标签：Forever,Winter,int,graph,vertices,each,test,output
From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17517686.html