ghizi

#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#define inf "ghizi.in"
#define outf "ghizi.out"
#define NMax 5100
#define VMax 103
#define INF 0x3f3f3f3f
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N,K;
int viz[VMax];
int C[VMax][VMax],F[VMax][VMax];
int T[VMax];

const int s = 102;
const int d = 101;

vector<int> LA[VMax];

struct arc { int x,y,uz; } G[NMax];

void read()
{
    f>>N>>K;;
    int t1,t2;
    for(int i=1; i<=N; i++)
    {
        f>>t1>>t2;
        C[t1+1][t2+1]++;
        LA[t1+1].push_back(t2+1); LA[t2+1].push_back(t1+1);
        G[i].x = t1+1; G[i].y = t2+1;
    }
    C[s][1] = K;
    LA[s].push_back(1); LA[1].push_back(s);
}

int bfs()
{
    queue<int> q;
    memset( viz, 0, sizeof(viz) );
    viz[s] = 1;
    q.push(s);
    while( !q.empty() )
    {
        int n = q.front(); q.pop();
        if( n==d ) continue;
        for(unsigned i=0; i<LA[n].size(); i++)
        {
            int x = LA[n][i];
            if( viz[x] || F[n][x] == C[n][x] ) continue;
            q.push(x);
            viz[x] = 1;
            T[x] = n;
        }
    }
    return viz[d];
}

inline int min(int a,int b) { return ( a<b ? a : b ); }

void flux()
{
    while( bfs() )
    {
        for(unsigned i=0; i<LA[d].size(); i++)
        {
            int v = LA[d][i];
            if( !viz[v] || F[v][d]==C[v][d] ) continue;
            T[d] = v;

            int fmin = INF;

            for( v = d; v!=s; v = T[v] )
                fmin = min( fmin, C[ T[v] ][v] - F[ T[v] ][v] );

            if( fmin==0 ) continue;

            for( v = d; v != s; v = T[v] )
            {
                F[ T[v] ][v] += fmin;
                F[v][ T[v] ] -=fmin;
            }
        }
    }
}

void print()
{
    int nr=0;
    for(int i=1; i<VMax-1; i++)
        for(int j=1; j<VMax-1; j++)
            if( F[i][j] )
                for(int p=1; p<=N; p++)
                    if( G[p].x==i && G[p].y==j && G[p].uz==0 ) { G[p].uz=1; nr++; break; }
    g<<nr<<"\n";
    for(int i=1; i<=N; i++)
        if( G[i].uz ) g<<i<<" ";
}

void solve()
{
    flux();
    print();
}

int main()
{
    read(); solve();
    f.close(); g.close();
    return 0;
}