SHARE
TWEET

B

a guest Apr 25th, 2013 1,071 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top