逼

王

晨

曦

没

鸡

鸡

接龙大成功@biggggod

666

再来 狗

笔

#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
bool b = false;
int visit[10000],stack,fir,sec,ans,x,y,a[10000][10000],n,m;
void make(int x){
stack++;
if (stack%2==0) visit [x] = 1;
else visit [x] = 2;
for (int i=1;i<=a[x][0];i++){
if (visit[a[x][i]]==0) {
make(a[x][i]);
if (stack%2==0) fir++;
else sec++;
}
else if (visit[a[x][i]]==visit[x]) b = false;
}
stack--;
}
int main(){
freopen("P1339.in" , "r" ,stdin);
freopen("P1339.out" , "w" , stdout);
scanf("%d%d" , &n ,&m);
memset(visit,0,sizeof(visit));
for (int i=1;i<=m;i++){
scanf("%d%d" , &x, &y);
a[x][0]++;a[x][a[x][0]] = y;
a[y][0]++;a[y][a[y][0]] = x;
}
/*for (int i=1;i<=n;i++){
for (int j=1;j<=a[i][0];j++)
printf("%d " , a[i][j]);
printf("\n");
}*/
b = true;
for (int i=1;i<=n;i++){
fir = 0 ; sec = 0; stack = 0;
if(visit[i]==0) make(i);
if(!b) {
printf("Impossible");
return 0;
}
ans+=min(fir,sec);
printf("%d %d\n" , fir ,sec);
}
printf("%d" , ans);
return 0;
}