#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <ios>
#include <map>
#include <set>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
#define N 100005
 
int par[N];
int last[N];
 
int getRoot(int x){
    if(par[x] == x) return x;
    return par[x] = getRoot(par[x]);
}
 
bool areSameComp(int a, int b){
    return getRoot(a) == getRoot(b);
}
 
void mergee(int a, int b){
    par[getRoot(a)] = getRoot(b);
}
 
int main() {
    int n, m, a, b;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        par[i] = i;
    }
    int tot = 0;
    for(int i = 0; i < m; i++){
        ++tot;
        scanf("%d %d", &a, &b);
        if(areSameComp(a, b)) break;
        if(last[a] != 0) mergee(last[a], b);
        if(last[b] != 0) mergee(last[b], a);
        if(areSameComp(a, b)) break;
        last[a] = b;
        last[b] = a;
    }
    
    cout << tot << endl;
    
    return 0;
}