Znzryb's Blog
0%

Posted on Edited on

思路讲解

https://codeforces.com/blog/entry/139415?locale=en

基本就是官方题解的思路

我们可以证明可以进行二操作的时候一定是先进行二操作的（说白了就那些数，+1了总归和后面相等的概率大一点），而不是先进行一操作

把所有2操作进行完了再进行1操作，我们可以证明，我们一定要将一个等于a1的数字发送到bag B，否则B中所有数字都大于a1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (idx <= N - 1) {
  if (A[idx] != A[idx + 1]) {
    cout << "No\n";
    return;
  } else {
    vis[A[idx + 1]] = true;
    idx += 2;  // 相当于将idx以及idx+1锁住(idx是因为要满足idx+1的需求，idx+1是因为移入了B)
    FOR(i, idx, N) {
      if (vis[A[i]]) {
        A[i] += 1;
      } else {
        break;
      }
    }
  }
// #ifdef LOCAL
  // FOR(i, 1, N) { cerr << A[i] << ' '; }
  // cerr << '\n';
// #endif
}
cout << "Yes\n";
}

AC代码

https://codeforces.com/contest/2067/submission/305772242

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Problem: B. Two Large Bags
// Contest: Codeforces - Codeforces Round 1004 (Div. 2)
// URL: https://codeforces.com/contest/2067/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(1e3) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T, A[MAXN], vis[MAXN];

inline void solve() {
  cin >> N;
  FOR(i, 1, N) {
    cin >> A[i];
    vis[i] = false;  // B这个袋子里有没有这个数字？
  }
  sort(A + 1, A + 1 + N);
  ll idx = 1;
  while (idx <= N - 1) {
    if (A[idx] != A[idx + 1]) {
      cout << "No\n";
      return;
    } else {
      vis[A[idx + 1]] = true;
      idx += 2;  // 相当于将idx以及idx+1锁住
      FOR(i, idx, N) {
        if (vis[A[i]]) {
          A[i] += 1;
        } else {
          break;
        }
      }
    }
// #ifdef LOCAL
    // FOR(i, 1, N) { cerr << A[i] << ' '; }
    // cerr << '\n';
// #endif
  }
  cout << "Yes\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
// #ifdef LOCAL
    // cerr << '\n';
// #endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2067/submission/305772242
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

其实还是挺简单的，不难，就是要分类讨论一下

前面搞着搞着搞错了，其实cnt→fi才是我们要加的

就是如果说我们不知道怎么排序或者什么，我们可以直接将答案算出来，取最大的答案就行了

1
2
3
4
5
6
7
8
9
10
11
12
lans -= 1;  // 先不管我们这个要做第二个操作的联通块
if (cnt.rbegin()->fi > 1) {
  // #ifdef LOCAL
  // cerr << lans << '\n';
  // #endif
  lans += cnt.rbegin()->fi;
} else if (cnt.rbegin()->fi == 1) {
  // #ifdef LOCAL
  // cerr<<"In if:" << i << ' ' << lans << '\n';
  // #endif
  lans += cnt.rbegin()->fi - 1;
}

AC代码

AC

https://codeforces.com/contest/2063/submission/305604041

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// Problem: C. Remove Exactly Two
// Contest: Codeforces - Codeforces Round 1000 (Div. 2)
// URL: https://codeforces.com/contest/2063/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T;
vector<ll> g[MAXN];
ll edges[MAXN];

inline void solve() {
  cin >> N;
  map<ll, ll> cnt;
  // 初始化
  FOR(i, 1, N) { g[i].clear(); }
  FOR(i, 1, N - 1) {
    ll u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  if (N == 2) {
    cout << 0 << '\n';
    return;
  }
  ll mx = 0, mxN = 1;
  FOR(i, 1, N) {
    edges[i] = SZ(g[i]);
    cnt[edges[i]] = cnt.find(edges[i]) == cnt.end() ? 1 : cnt[edges[i]] + 1;
  }
  ll ans = 0;
  map<ll, ll> backup = cnt;
  FOR(i, 1, N) {
    ll lans = edges[i];
    // #ifdef LOCAL
    // cerr << i << ' ' << edges[i] << '\n';
    // #endif
    cnt[edges[i]] -= 1;
    if (cnt[edges[i]] == 0) {
      cnt.erase(edges[i]);
    }
    FOR(j, 0, SZ(g[i]) - 1) {
      ll node = g[i][j];
      cnt[edges[node]] -= 1;
      cnt[edges[node] - 1] = cnt.find(edges[node] - 1) == cnt.end() ? 1 : cnt[edges[node] - 1] + 1;
      if (cnt[edges[node]] == 0) {
        cnt.erase(edges[node]);
      }
    }
    lans -= 1;  // 先不管我们这个要做第二个操作的联通块
    if (cnt.rbegin()->fi > 1) {
      // #ifdef LOCAL
      // cerr << lans << '\n';
      // #endif
      lans += cnt.rbegin()->fi;
    } else if (cnt.rbegin()->fi == 1) {
      // #ifdef LOCAL
      // cerr<<"In if:" << i << ' ' << lans << '\n';
      // #endif
      lans += cnt.rbegin()->fi - 1;
    }

    // #ifdef LOCAL
    // cerr << i << ' ' << lans << '\n';
    // #endif
    ans = max(ans, lans);
    cnt = backup;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
#ifdef LOCAL
    cerr << '\n';
#endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2063/submission/305604041
1
5
1 2
1 3
2 4
3 5

3

1
3
1 2
1 3

1
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

我们将不匹配的位置分类，发现最多只有四类，ab 分别是 00*,* 01*,* 10*,* 11 ，任意
两个不同种类不匹配的话，我们一定可以交换其中的某一位 0 和 1 使之两两匹配，

其他的没什么特殊的，我们发现四种情况全部都可以选择其他另外一种情况抵消。

那么问题就来到了怎么样抵消的问题上

我们一定可以交换其中的某一位 0 和 1 使之两两匹配，那么我
们就只看最多的一类不匹配的位置的数量有没有超过总数的一半即可。
如果超过就超过的部分反置，其余匹配，否则一定存在一种分配方式使之匹配后至多
仅剩一个。

官解的匹配方式是这样的，但我相信这个分类讨论大抵是没那么容易想到的，那我们有没有一种策略去匹配不出错那？

用大的去匹配次大的

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75564916

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
priority_queue<ll> pq;
pq.push(rem0);
pq.push(rem1);
pq.push(rem01);
pq.push(rem10);
ll ans=0;
while (SZ(pq) != 1) {
  ll u = pq.top();
  pq.pop();
  ll v = pq.top();
  pq.pop();
  ans += v * Y;
  if (u == v) continue;
  pq.push(u - v);
}
ans += pq.top() * X;

用大的去匹配小的

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75565204

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
priority_queue<ll> pq;
pq.push(rem0);
pq.push(rem1);
pq.push(rem01);
pq.push(rem10);
ll ans = 0;
while (SZ(pq) > 1) {
  ll u = pq.top();
  pq.pop();
  ll v = pq.top();
  pq.pop();
  ans += v * Y;
  pq.push(u - v);
}
if (pq.empty()) {
  cout << ans << '\n';
  return 0;
}
ans += pq.top() * X;
cout << ans << '\n';

似乎都会出问题，这些贪心策略都有瑕疵（见以下hack数据3，5，7，13）

1
2
3
4
5
6
7
28 5 6
0001111100000001111111111111
0001111111111110000000000000
1111111100000000000000000000

应该输出
84（14次交换*6=84）

有些人~~（我）~~可能觉得3，5，7，13根本无法消除（无法完全通过交换消除），通过交换最终会剩余2

但实际上是可以的，只不过比较复杂，需要通过分段的方法消除，具体见下

image

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75568259

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Problem: 小L的位运算
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95337/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
constexpr ll MAXN = static_cast<ll>(1e6) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, X, Y, T;
char A[MAXN], B[MAXN], C[MAXN];
// ll rem[7];
ll rem1, rem0, rem10, rem01;
// vector<ll> pq;
// ll ans=INF;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> X >> Y;
  FOR(i, 1, N) { cin >> A[i]; }
  FOR(i, 1, N) { cin >> B[i]; }
  FOR(i, 1, N) { cin >> C[i]; }
  FOR(i, 1, N) {
    if (((A[i] - '0') ^ (B[i] - '0')) != (C[i] - '0')) {
      if (C[i] == '1') {
        if (A[i] == '0' && B[i] == '0') {
          rem0 += 1;
        } else {
          rem1 += 1;
        }
      } else {
        if (A[i] == '1') {
          rem10 += 1;
        } else {
          rem01 += 1;
        }
      }
    }
  }
  // rem[0]=rem0,rem[1]=rem1,rem[2]=rem10,rem[3]=rem01;
  if (X * 2 > Y) {
    ll sum=rem0+rem1+rem10+rem01;
    ll maxR=max({rem0,rem1,rem10,rem01});
    ll ans=0;
    if(maxR*2<=sum){
    	ans=sum/2*Y+sum%2*X;
    }else{
    	ans=(maxR-(sum-maxR))*X+(sum-maxR)*Y;
    }
    cout << ans << '\n';
  } else {
    cout << (rem1 + rem0 + rem10 + rem01) * X << '\n';
  }
  return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

哈哈，不知道还可以这样分段消除，还以为题目出问题了，我太菜了

Posted on Edited on

思路讲解

image

倒过来找，不断的找树状数组上第pi个空位

这样做是对的原因是前面的被占的都是后来者，你是先来的，所以你只用管空白位置，完全不用管被占的位置

AC代码

AC

https://atcoder.jp/contests/abc392/submissions/62634320

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// Problem: F - Insert
// Contest: AtCoder - Japan Registry Services (JPRS) Programming Contest 2025#1
// (AtCoder Beginner Contest 392) URL:
// https://atcoder.jp/contests/abc392/tasks/abc392_f Memory Limit: 1024 MB Time
// Limit: 2000 ms by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(5e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T, P[MAXN], ans[MAXN];

struct BIT {  // 普通的单点修改区间查询树状数组（依赖MAXN）
  ll tr[MAXN];
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    FOR(i, 1, n) { tr[i] = 0; }
  }
  inline void add(int p, int x) {
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx+1;	// 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};

inline void solve() {
  cin >> N;
  BIT cnt(N);
  FOR(i, 1, N) { cin >> P[i]; }
  ROF(i, N, 1) {
    ll p = cnt.findKth(P[i]);  // 所有之后要在P[i]之前的都会影响i的摆放
    ans[p] = i;
    cnt.add(p, 1);
  }
  FOR(i, 1, N) { cout << ans[i] << ' '; }
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();

  return 0;
}
/*
AC
https://atcoder.jp/contests/abc392/submissions/62634320
9
1 2 2 4 5 2 3 2 3

1 8 9 6 7 3 2 4 5

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

为什么这道题目可以用类似于双指针的东西做出来？

其实有点类似于我最早的思路，就是已经合并过的就不管了。

不过他是以边为主视角的，这个还是比较新颖的，我之前的都是以块为主视角的，但块存在自环，重边，没边等等情况，总之肯定没有以边为主视角方便。

image

AC代码

https://atcoder.jp/contests/abc392/submissions/62618534

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T;
vector<pll> g[MAXN];
pll ab[MAXN];
bool isRem[MAXN];

struct DSU {  // referred jiangly
  int fa[MAXN], siz[MAXN], ln;
  DSU(int n) {
    ln = n;
    FOR(i, 1, n) {
      fa[i] = i;
      siz[i] = 1;
    }
  }
  int find(int x) {
    while (fa[x] != x) {
      x = fa[x];
      fa[x] = fa[fa[x]];
    }
    return x;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    siz[x] += siz[y];
    fa[y] = x;
    return true;
  }
  int size(int x) { return siz[find(x)]; }
  int countFa() {
    int res = 0;
    FOR(i, 1, ln) {
      if (fa[i] == i) ++res;
    }
    return res;
  }
};

inline void solve() {
  cin >> N >> M;
  DSU dsu(N);
  FOR(i, 1, M) {
    cin >> ab[i].fi >> ab[i].se;
    if (!dsu.merge(ab[i].fi, ab[i].se)) {  // 说明这条边是多余的
      isRem[i] = true;
    }
  }
  ll ans = dsu.countFa() - 1;
  ll flag = 1;
  cout << ans << '\n';
  FOR(i, 1, M) {
    if (ans <= 0) break;
    if (isRem[i]) {  // 只有多余的边才会进入
      FOR(j, flag, N) {
        if (!dsu.same(ab[i].fi, j)) {
          flag = j + 1;
          cout << i << ' ' << ab[i].se << ' ' << j << '\n';
          dsu.merge(ab[i].fi, j);
          --ans;
          break;
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
/*
AC
https://atcoder.jp/contests/abc392/submissions/62618534
*/

心路历程（WA，TLE，MLE……）

直接遍历还是有风险，合并还是要用dsu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// Problem: E - Cables and Servers
// Contest: AtCoder - Japan Registry Services (JPRS) Programming Contest 2025#1 (AtCoder Beginner Contest 392)
// URL: https://atcoder.jp/contests/abc392/tasks/abc392_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
vector<pll> g[MAXN];
ll fa[MAXN];
bool vis[MAXN];
vector<ll> root;
vector<pll> rem[MAXN];
pll ab[MAXN];

inline ll find(ll x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void dfs(ll x,ll pa){
	vis[x]=true;
	FOR(i,0,SZ(g[x])-1){
		ll fx=g[x][i].fi;
		if(vis[fx]) {
			// cerr<< fx <<' '<<pa<<'\n';
			if(fx!=pa) rem[find(fx)].pb({ab[g[x][i].se].se,g[x][i].se});
			continue;
		}
		fa[fx]=find(x);
		dfs(fx,x);
	}
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		ll a,b;
		cin>>a>>b;
		ab[i].fi=a,ab[i].se=b;
		if(a!=b){
			g[a].pb({b,i});
			g[b].pb({a,i});
		}else{
			g[a].pb({b,i});
		}
	}
	FOR(i,1,N){
		fa[i]=i;
	}
	
	FOR(i,1,N){
		if(vis[i]) continue;
		// cerr<<"OK\n";
		dfs(i,0);
	}
	set<ll> disCot;
	FOR(i,1,N){
		if(fa[i]==i) root.push_back(i),disCot.insert(i);
	}
	cout<<SZ(root)-1<<'\n';
	if(SZ(root)-1==0) return;
	disCot.erase(1);
	FOR(i,0,root.size()-1){
		if(disCot.empty()){
			break;
		}
		ll ri=root[i],start=0;
		if(SZ(rem[ri])>0){
			if(disCot.find(ri)!=disCot.end()){
				if(ri!=1) cout<<rem[ri][0].se<<' '<<rem[ri][0].fi<<' '<<1<<'\n',start=1;
				disCot.erase(ri);
			}
		}
		FOR(j,start,SZ(rem[ri])-1){
			if(disCot.empty()) return;
			cout<<rem[ri][j].se<<' '<<rem[ri][j].fi<<' '<< *disCot.begin()  <<'\n';
			disCot.erase(disCot.begin());	// 一定要在删之前判断是否为空
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	
	// FOR(i,1,N){
		// cerr<<i<<":\n";
		// FOR(j,0,SZ(rem[i])-1){
			// cerr<<rem[i][j].fi<<' '<< rem[i][j].se<<'\n';
		// }
		// cerr<<'\n';
	// }	
	return 0;
}
/*
WA*9
https://atcoder.jp/contests/abc392/submissions/62570130
排除返祖边处理问题
8 8
1 2
1 3
1 3
4 5
5 6
6 8
8 7
7 5

1
3 3 4


排除连接问题（有的联通块未连接）
6 5
1 2
1 2
1 3
5 6
5 6

2
2 2 4
5 6 1


*/