#include<bits/stdc++.h>
#define REP(i,n) for (int i = 1; i <= n; i++)
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define lli long long int
#define INF 1000000000
#define endl '\n'
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;
set<int> ar[100001];
vii bridges;
int in[100001] , low[100001] , vis[100001];
int timer;
//code for finding bridges can be found at https://c...content-available-to-author-only...s.com/graph/bridge-searching.html
//below function is also the implementation of the same algorithm
void dfs(int node , int p = -1)
{
vis[node] = 1;
in[node] = low[node] = timer++;
for(int child : ar[node])
{
if(child == p) continue;
if(vis[child])
low[node] = min(low[node] , in[child]);
else
{
dfs(child , node);
low[node] = min(low[node] , low[child]);
if(low[child] > in[node]) //this edge is a bridge
{
bridges.pb({node , child});
}
}
}
}
// function to mark all the elements from the same connected component
void dfs0(int node)
{
vis[node] = 1;
for(int child : ar[node])
if(!vis[child])
dfs0(child);
}
//function returns true if a cycle is found
bool hasCycle(int node ,int p = -1)
{
vis[node] = 1;
for(int child : ar[node])
if(child != p)
{
if(vis[child])
return true;
if(hasCycle(child , node))
return true;
}
return false;
}
int main()
{
int n , m , x , y ,t;
cin>>t;
while(t--)
{
cin>>n>>m , timer = 0 , bridges.clear();
REP(i , n) ar[i].clear() , vis[i] = 0;
REP(i , m)
{
cin>>x>>y;
ar[x].insert(y) , ar[y].insert(x);
}
//finding all the bridges
REP(i , n)
if(!vis[i])
dfs(i);
//removing all the bridges
for(ii e : bridges)
ar[e.ff].erase(e.ss) , ar[e.ss].erase(e.ff);
REP(i , n) vis[i] = 0;
//counting CC with cycles
int cycleCount = 0;
REP(i , n)
if(ar[i].size() > 0 && !vis[i])
dfs0(i) , cycleCount++;
if(cycleCount != 1)
cout<<"-1\n";
else
{
int maxDegree = 0;
int resNode = INF;
//finding node with highest degree
REP(i , n)
if(ar[i].size() > maxDegree)
maxDegree = ar[i].size() , resNode = i;
else
if(ar[i].size() == maxDegree)
resNode = min(resNode , i);
//removing all the edges of the highest degree node
REP(i , n) ar[i].erase(resNode) , vis[i] = 0;
ar[resNode].clear();
//checking if no cycle exist
REP(i , n)
if(!vis[i])
{
if(hasCycle(i))
{
//if a cucle is found res sould be -1
resNode = -1;
break;
}
}
cout<<resNode<<endl;
}
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBSRVAoaSxuKSBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIGlpIHBhaXI8aW50LGludD4KI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3I8aWk+CiNkZWZpbmUgbGxpIGxvbmcgbG9uZyBpbnQKI2RlZmluZSBJTkYgMTAwMDAwMDAwMAojZGVmaW5lIGVuZGwgJ1xuJwpjb25zdCBkb3VibGUgUEkgPSAzLjE0MTU5MjY1MzU4OTc5MzIzODQ2MDsKdHlwZWRlZiBzdGQ6OmNvbXBsZXg8ZG91YmxlPiBDb21wbGV4Owp0eXBlZGVmIHN0ZDo6dmFsYXJyYXk8Q29tcGxleD4gQ0FycmF5OwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKc2V0PGludD4gYXJbMTAwMDAxXTsKdmlpIGJyaWRnZXM7CmludCBpblsxMDAwMDFdICwgbG93WzEwMDAwMV0gLCB2aXNbMTAwMDAxXTsKaW50IHRpbWVyOwoKCi8vY29kZSBmb3IgZmluZGluZyBicmlkZ2VzIGNhbiBiZSBmb3VuZCBhdCBodHRwczovL2MuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnMuY29tL2dyYXBoL2JyaWRnZS1zZWFyY2hpbmcuaHRtbAovL2JlbG93IGZ1bmN0aW9uIGlzIGFsc28gdGhlIGltcGxlbWVudGF0aW9uIG9mIHRoZSBzYW1lIGFsZ29yaXRobQp2b2lkIGRmcyhpbnQgbm9kZSAsIGludCBwID0gLTEpCnsKCXZpc1tub2RlXSA9IDE7Cglpbltub2RlXSA9IGxvd1tub2RlXSA9IHRpbWVyKys7Cglmb3IoaW50IGNoaWxkIDogYXJbbm9kZV0pCgl7CgkJaWYoY2hpbGQgPT0gcCkgY29udGludWU7CgkJCgkJaWYodmlzW2NoaWxkXSkKCQlsb3dbbm9kZV0gPSBtaW4obG93W25vZGVdICwgaW5bY2hpbGRdKTsKCQkKCQllbHNlCgkJewoJCQlkZnMoY2hpbGQgLCBub2RlKTsKCQkJbG93W25vZGVdID0gbWluKGxvd1tub2RlXSAsIGxvd1tjaGlsZF0pOwoJCQkKCQkJaWYobG93W2NoaWxkXSA+IGluW25vZGVdKQkvL3RoaXMgZWRnZSBpcyBhIGJyaWRnZQoJCQl7CgkJCQlicmlkZ2VzLnBiKHtub2RlICwgY2hpbGR9KTsKCQkJfQoJCX0KCX0KfQoKLy8gZnVuY3Rpb24gdG8gbWFyayBhbGwgdGhlIGVsZW1lbnRzIGZyb20gdGhlIHNhbWUgY29ubmVjdGVkIGNvbXBvbmVudAp2b2lkIGRmczAoaW50IG5vZGUpCnsKCXZpc1tub2RlXSA9IDE7Cglmb3IoaW50IGNoaWxkIDogYXJbbm9kZV0pCglpZighdmlzW2NoaWxkXSkKCWRmczAoY2hpbGQpOwp9CgoKLy9mdW5jdGlvbiByZXR1cm5zIHRydWUgaWYgYSBjeWNsZSBpcyBmb3VuZApib29sIGhhc0N5Y2xlKGludCBub2RlICxpbnQgcCA9IC0xKQp7Cgl2aXNbbm9kZV0gPSAxOwoJZm9yKGludCBjaGlsZCA6IGFyW25vZGVdKQoJaWYoY2hpbGQgIT0gcCkKCXsKCQlpZih2aXNbY2hpbGRdKQoJCXJldHVybiB0cnVlOwoJCQoJCWlmKGhhc0N5Y2xlKGNoaWxkICwgbm9kZSkpCgkJcmV0dXJuIHRydWU7Cgl9CgkKCXJldHVybiBmYWxzZTsKfQoKaW50IG1haW4oKQp7CglpbnQgbiAsIG0gLCB4ICwgeSAsdDsKCWNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQljaW4+Pm4+Pm0gLCB0aW1lciA9IDAgLCBicmlkZ2VzLmNsZWFyKCk7CgkJUkVQKGkgLCBuKSBhcltpXS5jbGVhcigpICwgdmlzW2ldID0gMDsKCQlSRVAoaSAsIG0pCgkJewoJCQljaW4+Png+Pnk7CgkJCWFyW3hdLmluc2VydCh5KSAsIGFyW3ldLmluc2VydCh4KTsKIAkJfQoJCQoJCQoJCS8vZmluZGluZyBhbGwgdGhlIGJyaWRnZXMKIAkJUkVQKGkgLCBuKQogCQlpZighdmlzW2ldKQogCQlkZnMoaSk7CiAJCQogCQkKIAkJLy9yZW1vdmluZyBhbGwgdGhlIGJyaWRnZXMKIAkJZm9yKGlpIGUgOiBicmlkZ2VzKQogCQlhcltlLmZmXS5lcmFzZShlLnNzKSAsIGFyW2Uuc3NdLmVyYXNlKGUuZmYpOwogCQlSRVAoaSAsIG4pIHZpc1tpXSA9IDA7CiAJCQogCQkvL2NvdW50aW5nIENDIHdpdGggY3ljbGVzCiAJCWludCBjeWNsZUNvdW50ID0gMDsKIAkJUkVQKGkgLCBuKQogCQlpZihhcltpXS5zaXplKCkgPiAwICYmICF2aXNbaV0pCiAJCWRmczAoaSkgLCBjeWNsZUNvdW50Kys7CiAJCQogCQkKIAkJaWYoY3ljbGVDb3VudCAhPSAxKQogCQljb3V0PDwiLTFcbiI7CiAJCWVsc2UKIAkJewogCQkJaW50IG1heERlZ3JlZSA9IDA7CiAJCQlpbnQgcmVzTm9kZSA9IElORjsKIAkJCQogCQkJCiAJCQkvL2ZpbmRpbmcgbm9kZSB3aXRoIGhpZ2hlc3QgZGVncmVlCiAJCQlSRVAoaSAsIG4pCiAJCQlpZihhcltpXS5zaXplKCkgPiBtYXhEZWdyZWUpCiAJCQltYXhEZWdyZWUgPSBhcltpXS5zaXplKCkgLCByZXNOb2RlID0gaTsKIAkJCWVsc2UKIAkJCWlmKGFyW2ldLnNpemUoKSA9PSBtYXhEZWdyZWUpCiAJCQlyZXNOb2RlID0gbWluKHJlc05vZGUgLCBpKTsKIAkJCQogCQkJCiAJCQkvL3JlbW92aW5nIGFsbCB0aGUgZWRnZXMgb2YgdGhlIGhpZ2hlc3QgZGVncmVlIG5vZGUKIAkJCVJFUChpICwgbikgYXJbaV0uZXJhc2UocmVzTm9kZSkgLCB2aXNbaV0gPSAwOwogCQkJYXJbcmVzTm9kZV0uY2xlYXIoKTsKIAkJCQogCQkJCiAJCQkvL2NoZWNraW5nIGlmIG5vIGN5Y2xlIGV4aXN0CiAJCQlSRVAoaSAsIG4pCiAJCQlpZighdmlzW2ldKQogCQkJewogCQkJCWlmKGhhc0N5Y2xlKGkpKQogCQkJCXsKIAkJCQkJLy9pZiBhIGN1Y2xlIGlzIGZvdW5kIHJlcyBzb3VsZCBiZSAtMQogCQkJCQlyZXNOb2RlID0gLTE7CiAJCQkJCWJyZWFrOwoJCQkJfQoJCQl9CiAJCQljb3V0PDxyZXNOb2RlPDxlbmRsOwoJCX0KCX0KfQo=