fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ii pair <int , int>
  9. #define iii pair <int , ii>
  10. #define se second
  11. #define fi first
  12. #define all(v) (v).begin() , (v).end()
  13. #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin())
  14. #define bit(x,i) (((x) >> (i)) & 1LL)
  15. #define flip(x,i) ((x) ^ (1LL << (i)))
  16. #define ms(d,x) memset(d , x , sizeof(d))
  17. #define exist __exist
  18. #define ends __ends
  19. #define visit visited
  20. #define left __left
  21. #define right __right
  22. #define prev __prev
  23. #define next __next
  24. #define sitingfake 1
  25. #define orz 1
  26. //constant
  27.  
  28. const long long mod = 1e9 + 7;
  29. const long long linf = 4557430888798830399LL;
  30. const long long nlinf = -4485090715960753727LL;
  31. const int inf = 1061109567;
  32. const int ninf = -1044266559;
  33. const int dx[] = {0 , -1 , 0 , 1};
  34. const int dy[] = {-1 , 0 , 1 , 0};
  35.  
  36. template<typename T> bool maximize(T &a, const T &b)
  37. {
  38.     if(a < b) {a = b; return 1;}
  39.     return 0;
  40. }
  41.  
  42. template<typename T> bool minimize(T &a, const T &b)
  43. {
  44.     if(a > b) {a = b; return 1;}
  45.     return 0;
  46. }
  47.  
  48. void Plus(ll & a ,ll b)
  49. {
  50.     b %= mod;
  51.     a += b;
  52.     if(a < 0) a += mod;
  53.     a %= mod;
  54.     return;
  55. }
  56.  
  57. void Mul(ll & a, ll b)
  58. {
  59.     (a *= (b % mod)) %= mod;
  60.     return;
  61. }
  62.  
  63. //code
  64. const int maxn = 303;
  65. vector <int> g[maxn];
  66. int n , m;
  67. bool d[maxn];
  68. bool edges[maxn][maxn];
  69. void reset()
  70. {
  71.     for(int i = 1; i <= n; i++)
  72.     {
  73.         d[i] = 0;
  74.         g[i].clear();
  75.     }
  76.     for(int i = 1; i <= n; i++)
  77.     {
  78.         for(int j = 1; j <= n; j++)
  79.         {
  80.             edges[i][j] = 0;
  81.         }
  82.     }
  83. }
  84. void solve(void)
  85. {
  86.     reset();
  87.     cin >> n >> m;
  88.  
  89.     for(int i = 1; i <= m; i++)
  90.     {
  91.         int u , v;
  92.         cin >> u >> v;
  93.         if(u > v) swap(u , v);
  94.         g[u].push_back(v);
  95.         g[v].push_back(u);
  96.         edges[u][v] = edges[v][u] = 1;
  97.     }
  98.     if(n < 5)
  99.     {
  100.         cout << -1 << "\n";
  101.         return;
  102.     }
  103.     for(int i = 1; i <= n; i++) sort(all(g[i]));
  104.     for(int i = 1; i <= n; i++)
  105.     {
  106.         bool flag = 0;
  107.         for(int v : g[i]) d[v] = 1;
  108.         for(int v : g[i])
  109.         {
  110.             for(int w : g[v])
  111.             {
  112.                 if(d[w])
  113.                 {
  114.                     flag = 1;
  115.                     break;
  116.                 }
  117.             }
  118.             if(flag) break;
  119.         }
  120.         for(int v : g[i]) d[v] = 0;
  121.         if(flag)
  122.         {
  123.             for(int u = 1; u <= n; u++)
  124.             {
  125.                 for(int v = u + 1; v <= n; v++)
  126.                 {
  127.                     if(u != i && v != i && !edges[u][v] && !edges[v][i] && !edges[i][u])
  128.                     {
  129.                         cout << "5\n";
  130.                         return;
  131.                     }
  132.                 }
  133.             }
  134.         }
  135.     }
  136.     cout << -1 << "\n";
  137. }
  138. /**
  139. **/
  140. signed main()
  141. {
  142.    ios_base::sync_with_stdio(0);
  143.    cin.tie(0);
  144.    cout.tie(0);
  145.  
  146.    #define task "triple"
  147.  
  148.    if(fopen(task".inp","r"))
  149.    {
  150.        freopen(task".inp","r",stdin);
  151.        freopen(task".out","w",stdout);
  152.    }
  153.  
  154.    int tc = 1;
  155.    cin >> tc;
  156.    while(tc--) solve();
  157.  
  158. //   execute;
  159. }
  160.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/17ToHb
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!