Guest User

B

a guest
Apr 25th, 2013
2,702
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _SECURE_SCL 0
  3. #pragma comment(linker, "/STACK:300000000")
  4.  
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <cassert>
  8. #include <cctype>
  9. #include <complex>
  10. #include <ctime>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <deque>
  15. #include <functional>
  16. #include <fstream>
  17. #include <iostream>
  18. #include <iomanip>
  19. #include <map>
  20. #include <memory.h>
  21. #include <numeric>
  22. #include <queue>
  23. #include <set>
  24. #include <stack>
  25. #include <string>
  26. #include <sstream>
  27. #include <vector>
  28. #include <utility>
  29. #include <cmath>
  30. using namespace std;
  31.  
  32. #define pb push_back
  33. #define mp make_pair
  34. #define sz(a) (int)(a).size()
  35. #define all(a) (a).begin(), (a).end()
  36. #define rall(a) (a).rbegin(), (a).rend()
  37.  
  38. #define forn(i,n) for (int i=0; i<int(n); ++i)
  39. #define fornd(i,n) for (int i=int(n)-1; i>=0; --i)
  40. #define forab(i,a,b) for (int i=int(a); i<int(b); ++i)
  41.  
  42. typedef long long ll;
  43. typedef long double ld;
  44. typedef unsigned long long ull;
  45.  
  46. const int INF = (int) 1e9;
  47. const long long INF64 = (long long) 1e18;
  48. const long double eps = 1e-9;
  49. const long double pi = 3.14159265358979323846;
  50.  
  51. int g[50][50], n, m;
  52. bool used[50];
  53.  
  54. vector <int> cur;
  55.  
  56. vector <vector <int> > c[50];
  57.  
  58. void dfs(int v){
  59.     used[v] = true;
  60.     cur.pb(v);
  61.     for (int i=1; i<=n; i++)
  62.         if (g[v][i] && !used[i])
  63.             dfs(i);
  64. }
  65.  
  66. int main(){
  67. #ifdef dudkamaster
  68.     freopen("input.txt","rt",stdin);
  69.     freopen("output.txt","wt",stdout);
  70. #endif
  71.     memset(g, 0, sizeof(g));
  72.     memset(used, 0, sizeof(used));
  73.     cin >> n >> m;
  74.     for (int i=0; i<m; i++){
  75.         int a,b;
  76.         cin >> a >> b;
  77.         g[a][b] = g[b][a] = 1;
  78.     }
  79.     for (int i=1; i<=n; i++){
  80.         if (!used[i]){
  81.             cur.clear();
  82.             dfs(i);
  83.             c[sz(cur)].pb(cur);
  84.         }
  85.     }
  86.     vector <vector <int> > out = c[3];
  87.     for (int i=4; i<50; i++){
  88.         if (sz(c[i])!=0){
  89.             cout << -1;
  90.             return 0;
  91.         }
  92.     }
  93.     if (sz(c[2])>sz(c[1])){
  94.         cout << -1;
  95.         return 0;
  96.     }
  97.     if ((sz(c[1])-sz(c[2])) % 3 != 0){
  98.         cout << -1;
  99.         return 0;
  100.     }
  101.     forn(i,sz(c[2])){
  102.         vector <int> tout;
  103.         tout.pb(c[2][i][0]);
  104.         tout.pb(c[2][i][1]);
  105.         tout.pb(c[1][i][0]);
  106.         out.pb(tout);
  107.     }
  108.     for (int i=sz(c[2]); i<sz(c[1]); i += 3){
  109.         vector <int> tout;
  110.         forn(j,3)
  111.             tout.pb(c[1][i+j][0]);
  112.         out.pb(tout);
  113.     }
  114.     forn(i,n/3){
  115.         forn(j,3)
  116.             cout << out[i][j] << ' ';
  117.         cout << endl;
  118.     }
  119.            
  120.     return 0;
  121. }
RAW Paste Data