#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double pi = acos(-1.0);
const int maxn = 200000 + 10;
const int mod = 1e9 + 7;
inline char _getchar() {
  static const int BUFSIZE = 100001;
  static char buf[BUFSIZE];
  static char *psta = buf, *pend = buf;
  if (psta >= pend) {
    psta = buf;
    pend = buf + fread(buf, 1, BUFSIZE, stdin);
    if (psta >= pend) return -1;
  }
  return *psta++;
}
inline int read(int &x) {
  x = 0;
  int f = 1;
  char ch = _getchar();
  while ((ch < '0' || ch > '9') && ~ch) {
    if (ch == '-') f = -1;
    ch = _getchar();
  }
  if (ch == -1) return -1;
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = _getchar();
  }
  x *= f;
  return 1;
}
inline int read(long long &x) {
  x = 0;
  int f = 1;
  char ch = _getchar();
  while ((ch < '0' || ch > '9') && ~ch) {
    if (ch == '-') f = -1;
    ch = _getchar();
  }
  if (ch == -1) return -1;
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = _getchar();
  }
  x *= f;
  return 1;
}
inline int read(double &x) {
  char in;
  double Dec = 0.1;
  bool IsN = false, IsD = false;
  in = _getchar();
  if (in == EOF) return -1;
  while (in != '-' && in != '.' && (in < '0' || in > '9')) in = _getchar();
  if (in == '-') {
    IsN = true;
    x = 0;
  } else if (in == '.') {
    IsD = true;
    x = 0;
  } else
    x = in - '0';
  if (!IsD) {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x *= 10;
      x += in - '0';
    }
  }
  if (in != '.') {
    if (IsN) x = -x;
    return 1;
  } else {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x += Dec * (in - '0');
      Dec *= 0.1;
    }
  }
  if (IsN) x = -x;
  return 1;
}
inline int read(float &x) {
  char in;
  double Dec = 0.1;
  bool IsN = false, IsD = false;
  in = _getchar();
  if (in == EOF) return -1;
  while (in != '-' && in != '.' && (in < '0' || in > '9')) in = _getchar();
  if (in == '-') {
    IsN = true;
    x = 0;
  } else if (in == '.') {
    IsD = true;
    x = 0;
  } else
    x = in - '0';
  if (!IsD) {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x *= 10;
      x += in - '0';
    }
  }
  if (in != '.') {
    if (IsN) x = -x;
    return 1;
  } else {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x += Dec * (in - '0');
      Dec *= 0.1;
    }
  }
  if (IsN) x = -x;
  return 1;
}
inline int read(char *x) {
  char *tmp = x;
  char in = _getchar();
  while (in <= ' ' && in != EOF) in = _getchar();
  if (in == -1) return -1;
  while (in > ' ') *(tmp++) = in, in = _getchar();
  *tmp = '\0';
  return 1;
}
int l[maxn], r[maxn];
vector<int> nt[maxn];
vector<int> pt[maxn];
int cnt[maxn];
int vis[maxn];
int tot;
int ans[maxn];
int ok[maxn];
int n, m, k;
queue<int> q;
void Count() {
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    tot--;
    for (int i = 0; i < nt[x].size(); i++) {
      int nx = nt[x][i];
      if (!vis[nx]) {
        if (!ok[pt[x][i]]) cnt[nx]--;
        if (cnt[nx] < k) q.push(nx), vis[nx] = 1;
      }
      ok[pt[x][i]] = 1;
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", l + i, r + i);
    nt[l[i]].push_back(r[i]), nt[r[i]].push_back(l[i]);
    pt[l[i]].push_back(i), pt[r[i]].push_back(i);
    cnt[l[i]]++, cnt[r[i]]++;
  }
  tot = n;
  for (int i = 1; i <= n; i++)
    if (cnt[i] < k) q.push(i), vis[i] = 1;
  Count();
  for (int i = m - 1; i >= 0; i--) {
    ans[i] = tot;
    ok[i] = 1;
    if ((!vis[l[i]]) && (!vis[r[i]])) {
      cnt[l[i]]--, cnt[r[i]]--;
      if (cnt[l[i]] < k) q.push(l[i]), vis[l[i]] = 1;
      if (cnt[r[i]] < k) q.push(r[i]), vis[r[i]] = 1;
      Count();
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

There are n persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.

We want to plan a trip for every evening of m days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold: 

  * Either this person does not go on the trip, 
  * Or at least k of his friends also go on the trip. 



Note that the friendship is not transitive. That is, if a and b are friends and b and c are friends, it does not necessarily imply that a and c are friends.

For each day, find the maximum number of people that can go on the trip on that day.

Input

The first line contains three integers n, m, and k (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m ≤ 2 ⋅ 10^5, 1 ≤ k < n) — the number of people, the number of days and the number of friends each person on the trip should have in the group.

The i-th (1 ≤ i ≤ m) of the next m lines contains two integers x and y (1≤ x, y≤ n, x≠ y), meaning that persons x and y become friends on the morning of day i. It is guaranteed that x and y were not friends before.

Output

Print exactly m lines, where the i-th of them (1≤ i≤ m) contains the maximum number of people that can go on the trip on the evening of the day i.

Examples

Input

4 4 2
2 3
1 2
1 3
1 4


Output

0
0
3
3


Input

5 8 2
2 1
4 2
5 4
5 2
4 3
5 1
4 1
3 2


Output

0
0
0
3
3
4
4
5


Input

5 7 2
1 5
3 2
2 5
3 4
1 2
5 3
1 3


Output

0
0
0
0
3
4
4

Note

In the first example, 

  * 1,2,3 can go on day 3 and 4. 



In the second example, 

  * 2,4,5 can go on day 4 and 5. 
  * 1,2,4,5 can go on day 6 and 7. 
  * 1,2,3,4,5 can go on day 8. 



In the third example, 

  * 1,2,5 can go on day 5. 
  * 1,2,3,5 can go on day 6 and 7. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double pi = acos(-1.0);
const int maxn = 200000 + 10;
const int mod = 1e9 + 7;
inline char _getchar() {
  static const int BUFSIZE = 100001;
  static char buf[BUFSIZE];
  static char *psta = buf, *pend = buf;
  if (psta >= pend) {
    psta = buf;
    pend = buf + fread(buf, 1, BUFSIZE, stdin);
    if (psta >= pend) return -1;
  }
  return *psta++;
}
inline int read(int &x) {
  x = 0;
  int f = 1;
  char ch = _getchar();
  while ((ch < '0' || ch > '9') && ~ch) {
    if (ch == '-') f = -1;
    ch = _getchar();
  }
  if (ch == -1) return -1;
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = _getchar();
  }
  x *= f;
  return 1;
}
inline int read(long long &x) {
  x = 0;
  int f = 1;
  char ch = _getchar();
  while ((ch < '0' || ch > '9') && ~ch) {
    if (ch == '-') f = -1;
    ch = _getchar();
  }
  if (ch == -1) return -1;
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = _getchar();
  }
  x *= f;
  return 1;
}
inline int read(double &x) {
  char in;
  double Dec = 0.1;
  bool IsN = false, IsD = false;
  in = _getchar();
  if (in == EOF) return -1;
  while (in != '-' && in != '.' && (in < '0' || in > '9')) in = _getchar();
  if (in == '-') {
    IsN = true;
    x = 0;
  } else if (in == '.') {
    IsD = true;
    x = 0;
  } else
    x = in - '0';
  if (!IsD) {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x *= 10;
      x += in - '0';
    }
  }
  if (in != '.') {
    if (IsN) x = -x;
    return 1;
  } else {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x += Dec * (in - '0');
      Dec *= 0.1;
    }
  }
  if (IsN) x = -x;
  return 1;
}
inline int read(float &x) {
  char in;
  double Dec = 0.1;
  bool IsN = false, IsD = false;
  in = _getchar();
  if (in == EOF) return -1;
  while (in != '-' && in != '.' && (in < '0' || in > '9')) in = _getchar();
  if (in == '-') {
    IsN = true;
    x = 0;
  } else if (in == '.') {
    IsD = true;
    x = 0;
  } else
    x = in - '0';
  if (!IsD) {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x *= 10;
      x += in - '0';
    }
  }
  if (in != '.') {
    if (IsN) x = -x;
    return 1;
  } else {
    while (in = _getchar(), in >= '0' && in <= '9') {
      x += Dec * (in - '0');
      Dec *= 0.1;
    }
  }
  if (IsN) x = -x;
  return 1;
}
inline int read(char *x) {
  char *tmp = x;
  char in = _getchar();
  while (in <= ' ' && in != EOF) in = _getchar();
  if (in == -1) return -1;
  while (in > ' ') *(tmp++) = in, in = _getchar();
  *tmp = '\0';
  return 1;
}
int l[maxn], r[maxn];
vector<int> nt[maxn];
vector<int> pt[maxn];
int cnt[maxn];
int vis[maxn];
int tot;
int ans[maxn];
int ok[maxn];
int n, m, k;
queue<int> q;
void Count() {
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    tot--;
    for (int i = 0; i < nt[x].size(); i++) {
      int nx = nt[x][i];
      if (!vis[nx]) {
        if (!ok[pt[x][i]]) cnt[nx]--;
        if (cnt[nx] < k) q.push(nx), vis[nx] = 1;
      }
      ok[pt[x][i]] = 1;
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", l + i, r + i);
    nt[l[i]].push_back(r[i]), nt[r[i]].push_back(l[i]);
    pt[l[i]].push_back(i), pt[r[i]].push_back(i);
    cnt[l[i]]++, cnt[r[i]]++;
  }
  tot = n;
  for (int i = 1; i <= n; i++)
    if (cnt[i] < k) q.push(i), vis[i] = 1;
  Count();
  for (int i = m - 1; i >= 0; i--) {
    ans[i] = tot;
    ok[i] = 1;
    if ((!vis[l[i]]) && (!vis[r[i]])) {
      cnt[l[i]]--, cnt[r[i]]--;
      if (cnt[l[i]] < k) q.push(l[i]), vis[l[i]] = 1;
      if (cnt[r[i]] < k) q.push(r[i]), vis[r[i]] = 1;
      Count();
    }
  }
  for (int i = 0; i < m; i++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

```