fork download
  1. /*#include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <stack>
  8. #include <queue>
  9. #include <cmath>
  10. #include <algorithm>
  11.  */
  12. #include <bits/stdc++.h>
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef vector<int> vi;
  17. typedef pair<int, int> ii;
  18. typedef vector<ii> vii;
  19. typedef set<int> si;
  20. typedef map<string, int> msi;
  21. typedef stack<long long> ss;
  22. #define get(a) #a
  23.  
  24. //#define DEBUG
  25. //#define local
  26.  
  27. #define endl '\n'
  28.  
  29. #ifdef DEBUG
  30.  
  31. #define debug(args...) {dbg,args; cerr<<endl;}
  32.  
  33. #else
  34.  
  35. #define debug(args...) // Just strip off all debug tokens
  36.  
  37. #endif
  38.  
  39. struct debugger
  40.  
  41. {
  42.  
  43. template<typename T> debugger& operator , (const T& v)
  44.  
  45. {
  46.  
  47. cerr<<v<<" ";
  48.  
  49. return *this;
  50.  
  51. }
  52.  
  53. } dbg;
  54.  
  55. #define INF 1000000000
  56. int main(){
  57. std::ios::sync_with_stdio(false);
  58. #ifdef local
  59. freopen("in.txt","r",stdin);
  60. #endif
  61.  
  62. int n,m;
  63. cin>>n>>m;
  64.  
  65. int min_sum = INF;
  66.  
  67. vector< vector<int> > arr;
  68. vector< pair<int,int> > p;
  69. for(int i = 0;i < n;i++){
  70. vector<int> q(m,0);
  71. arr.push_back(q);
  72. }
  73.  
  74.  
  75. int a,b,c;
  76. for (int i = 0; i < m; ++i)
  77. {
  78. cin>>a>>b;
  79.  
  80. a--;
  81. b--;
  82. arr[a][b] = 1;
  83. arr[b][a] = 1;
  84. p.push_back(make_pair(a,b));
  85. }
  86.  
  87.  
  88. vector<vector<int> > v;
  89.  
  90. int sum[n];
  91.  
  92. for(int i = 0;i < n;i++){
  93. int sums = 0;
  94. vector<int> q;
  95. //q.push_back(-1);
  96. for(int j = 0;j < m;j++){
  97. sums += arr[i][j];
  98. if(arr[i][j])
  99. q.push_back(j);
  100. }
  101. v.push_back(q);
  102. sum[i] = sums;
  103. }
  104.  
  105. arr.clear();
  106. vector<int>::iterator it;
  107. for(int i = 0;i < p.size();i++){
  108. a = p[i].first;
  109. b = p[i].second;
  110. for(int j = i+1;j < p.size();j++){
  111. if(p[j].first == a){
  112. if(v[b].size() > 0){
  113. it = lower_bound(v[b].begin(),v[b].end(),p[j].second);
  114. if(*it == p[j].second){
  115. //cout<<a<<" "<<b<<" "<<p[j].second<<endl;
  116. min_sum = min(min_sum,sum[a] + sum[b] + sum[p[j].second] - 6);
  117. }
  118. }
  119. }
  120. if(p[j].second == a){
  121. if(v[b].size() > 0){
  122. it = lower_bound(v[b].begin(),v[b].end(),p[j].first);
  123. if(*it == p[j].first){
  124. //cout<<a<<" "<<b<<" "<<p[j].first<<" minsum = "<<min_sum<<endl;
  125. min_sum = min(min_sum,sum[a] + sum[b] + sum[p[j].first] - 6);
  126. }
  127. }
  128. }
  129. }
  130. }
  131.  
  132. if(min_sum == INF){
  133. cout<<"-1\n";
  134. }
  135. else{
  136. cout<<min_sum<<endl;
  137. }
  138.  
  139. }
Success #stdin #stdout 0s 3412KB
stdin
3 2
2 3
2 1
stdout
-1