#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
vector<int> v[maxn];
pair<long long, long long> a[maxn];
long long q[maxn], siz[maxn];
bool c[maxn];
long long n, m, k;
set<pair<long long, long long> > s;
map<pair<long long, long long>, bool> mark;
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (long long y = 0; y < m; y++) {
    cin >> a[y].first >> a[y].second;
    v[a[y].first].push_back(a[y].second), v[a[y].second].push_back(a[y].first);
    siz[a[y].second]++, siz[a[y].first]++;
  }
  for (long long y = 1; y <= n; y++)
    s.insert(pair<long long, long long>(siz[y], y));
  for (long long y = m - 1; y >= 0; y--) {
    if (y != m - 1 && !mark[a[y + 1]]) {
      mark[pair<long long, long long>(a[y + 1].second, a[y + 1].first)] =
          mark[pair<long long, long long>(a[y + 1].first, a[y + 1].second)] = 1;
      long long i = a[y + 1].second;
      siz[i]--;
      if (c[i] == 0) {
        pair<long long, long long> x =
            pair<long long, long long>(siz[i] + 1, i);
        s.erase(x);
        x.first--;
        s.insert(x);
      }
      i = a[y + 1].first;
      siz[i]--;
      if (c[i] == 0) {
        pair<long long, long long> x =
            pair<long long, long long>(siz[i] + 1, i);
        s.erase(x);
        x.first--;
        s.insert(x);
      }
    }
    while (s.size() != 0) {
      pair<long long, long long> x = *s.begin();
      if (x.first >= k) break;
      s.erase(x);
      c[x.second] = 1;
      for (long long ii = 0; ii < v[x.second].size(); ii++) {
        long long i = v[x.second][ii];
        if (!mark[pair<long long, long long>(x.second, i)]) {
          mark[pair<long long, long long>(x.second, i)] =
              mark[pair<long long, long long>(i, x.second)] = 1;
          siz[i]--;
          siz[x.second]--;
          if (!c[i]) {
            pair<long long, long long> z =
                pair<long long, long long>(siz[i] + 1, i);
            s.erase(z);
            z.first--;
            s.insert(z);
          }
        }
      }
    }
    q[y] = s.size();
  }
  for (long long y = 0; y < m; y++) cout << q[y] << endl;
}

### Prompt

Develop a solution in Cpp 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 maxn = 2e5 + 100;
vector<int> v[maxn];
pair<long long, long long> a[maxn];
long long q[maxn], siz[maxn];
bool c[maxn];
long long n, m, k;
set<pair<long long, long long> > s;
map<pair<long long, long long>, bool> mark;
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (long long y = 0; y < m; y++) {
    cin >> a[y].first >> a[y].second;
    v[a[y].first].push_back(a[y].second), v[a[y].second].push_back(a[y].first);
    siz[a[y].second]++, siz[a[y].first]++;
  }
  for (long long y = 1; y <= n; y++)
    s.insert(pair<long long, long long>(siz[y], y));
  for (long long y = m - 1; y >= 0; y--) {
    if (y != m - 1 && !mark[a[y + 1]]) {
      mark[pair<long long, long long>(a[y + 1].second, a[y + 1].first)] =
          mark[pair<long long, long long>(a[y + 1].first, a[y + 1].second)] = 1;
      long long i = a[y + 1].second;
      siz[i]--;
      if (c[i] == 0) {
        pair<long long, long long> x =
            pair<long long, long long>(siz[i] + 1, i);
        s.erase(x);
        x.first--;
        s.insert(x);
      }
      i = a[y + 1].first;
      siz[i]--;
      if (c[i] == 0) {
        pair<long long, long long> x =
            pair<long long, long long>(siz[i] + 1, i);
        s.erase(x);
        x.first--;
        s.insert(x);
      }
    }
    while (s.size() != 0) {
      pair<long long, long long> x = *s.begin();
      if (x.first >= k) break;
      s.erase(x);
      c[x.second] = 1;
      for (long long ii = 0; ii < v[x.second].size(); ii++) {
        long long i = v[x.second][ii];
        if (!mark[pair<long long, long long>(x.second, i)]) {
          mark[pair<long long, long long>(x.second, i)] =
              mark[pair<long long, long long>(i, x.second)] = 1;
          siz[i]--;
          siz[x.second]--;
          if (!c[i]) {
            pair<long long, long long> z =
                pair<long long, long long>(siz[i] + 1, i);
            s.erase(z);
            z.first--;
            s.insert(z);
          }
        }
      }
    }
    q[y] = s.size();
  }
  for (long long y = 0; y < m; y++) cout << q[y] << endl;
}

```