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
#include <bits/stdc++.h>
using namespace std;
#define fora(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)
constexpr int MOD = 1e9 + 7;
constexpr int INF = INT32_MAX;
constexpr int MAXN = 1e5 + 10;
constexpr double eps = 1e-8;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
using Vec = vector<int>;
template <class T> void Min(T &a, T b) {if (b < a) a = b;}
template <class T> void Max(T &a, T b) {if (b > a) a = b;}
ll N, M, K, T;
int diff[MAXN], grp[MAXN];
int X, Y;
void Init() {
  memset(diff, 0, sizeof(diff));
  memset(grp, 0, sizeof(grp));
}
int FindPa(int x) {
  if (grp[x] != 0) {
    int p = FindPa(grp[x]);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX