#include using namespace std; #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto&i:a) #define ff first #define ss second #define pb push_back #define all(a) begin(a),end(a) using vi=vector; using vll=vector; using ll=long long; using pii=pair; using pll=pair; inline bool ingrid(int a,int b,int h,int w){ return 0<=a&&a deg(n); rep(i,0,m){ if(pii(u[i],v[i])==pii(0,n-1)){ cout<<-1< ans(m,-1); if(max(deg.front(),deg.back())<=m/2){ vi cnt(2); rep(i,0,m){ if(u[i]==0){ cnt[0]++; ans[i]=0; } if(v[i]==n-1){ cnt[1]++; ans[i]=1; } } rep(i,0,m){ if(ans[i]!=-1)continue; if(cnt[0]>n>>m; u.resize(m);v.resize(m); rep(i,0,m){ cin>>u[i]>>v[i];u[i]--;v[i]--; } solve(); return 0; } /* */