#include /* #include #include using namespace __gnu_pbds; tree,rb_tree_tag,tree_order_statistics_node_update> t; */ //*t.find_by_order(x) element number x. //t.order_of_key(y) number of elements (x) where the compare function is true for x,y. using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; //Below classes and functions are created by SPatrik. ll good_rand() { return rand()*RAND_MAX+rand(); //A rand that returns higher values. } ll high_rand() { ll ran=rand()*RAND_MAX; ran*=RAND_MAX; ran+=rand()*RAND_MAX+rand(); return ran; //A rand that returns even higher values. } template //Additional functions: Automatic resize of the vector in case of using index of element that is not part of the vector. Print and read functions, to make input and output faster class myvector : public std::vector //read function has 2 parameters. A template (n) (operator (int)>n. If true, n must have defined cin>> If using print or read, the elements of the vector must have defined cin>> or cout<< { public: A& operator[](int pos) { if (pos<0) pos=0; while (this->size() <= pos) { this->push_back({}); } return std::vector::operator[](pos); } void print(bool b=false) { unsigned int si=this->size(); if (b) std::cout<operator[](i) << " "; } } void printendl(bool b=false) { print(b); std::cout << std::endl; } void good_random_shuffle() { unsigned int si=this->size(); for (unsigned int i=0; ioperator[](i), this->operator[](j)); } } template void read(B &n, bool b=false) { if (b) std::cin>>n; for (int i=0; i>this->operator[](i); } } void push_to(int pos, int val) { while (this->size()>pos) { int newval=this->operator[](pos); this->operator[](pos)=val; val=newval; ++pos; } this->operator[](pos)=val; } }; template class myqueue: public std::queue { public: A front() const { if (this->empty()) return{}; return std::queue::front(); } A top() const { return front(); } void pop() { if (this->empty()) return; std::queue::pop(); } A take() { A a = this->front(); this->pop(); return a; } void print(bool b=false) { while(!this->empty()) { std::cout<::value_type> >//1 or 2 arguments. Unlikely priority_queue, the second argument is the compare. If there are no elements of the priority_queue top() returns a default value (for example 0 if it is an int). class mypriority_queue : public std::priority_queue, B>//take() returns the top() value and also runs the pop() function. { public: A top() const { if (this->empty()) return{}; return std::priority_queue, B>::top(); } void pop() { if (this->empty()) return; std::priority_queue, B>::pop(); } A take() { A a = this->top(); this->pop(); return a; } void print(bool b=false) { while(!this->empty()) { std::cout<modvalue = 0; } modll(int x) { this->modvalue = x%mod; } modll(ll x) { this->modvalue = x % mod; } modll(const modll &x) { this->modvalue=x.modvalue; } ll getmodvalue() const { return modvalue; } static ll modpow(ll z, ll u) { if (u == 0) return 1; if (u == 1) return z; if (u % 2 == 0) { ll sa = modpow(z, u / 2); return (sa*sa) % mod; } return (z * modpow(z, u - 1)) % mod; } static modll fastpow(ll z, ll u) { modll a=modpow(z, u); return a; } static modll fact(ll z) { modll a=1; for (ll i=2; i<=z; ++i) { a*=i; } return a; } static modll choose(ll n, ll k) { modll a=1; //if (k>n/2) return choose(n, n-k); for (ll i=n; n-i+1<=k; --i) { modll b=i; a=a*b; } for (ll i=2; i<=k; ++i) { modll b=i; a=a/b; } return a; } ll rec() const { return modll::modpow(modvalue, mod - 2); } modll operator+(const modll &x) const { modll a; a.modvalue=(this->modvalue + x.modvalue) % mod; return a; } modll operator-(const modll &x) const { modll a; a.modvalue = (mod + this->modvalue - x.modvalue) % mod; return a; } modll operator*(const modll &x) const { modll a; a.modvalue = (this->modvalue * x.modvalue) % mod; return a; } modll operator/(const modll &x) const { modll a; if (x.modvalue == 0) return a; a.modvalue = (this->modvalue * x.rec()) % mod; return a; } template modll operator+(A x) const { if (x<0) return this->operator-(-x); modll a; a.modvalue=(this->modvalue+x%mod)%mod; return a; } template modll operator-(A x) const { if (x<0) return this->operator+(-x); modll a; a.modvalue=(this->modvalue-(x%mod)+mod)%mod; return a; } template modll operator*(A x) const { if (x<0) { ll y=x/mod; y*=mod; y=x-y; x=y; } x%=mod; modll a; a.modvalue=(this->modvalue*x)%mod; return a; } template modll operator/(A x) const { if (x<0) { ll y=x/mod; y*=mod; y=x-y; x=y; } x%=mod; modll a; if (x==0) return a; modll b=x; a=*this/b; return a; } void operator=(modll x) { this->modvalue = x.modvalue; } template void operator=(A x) { this->modvalue = x % mod; } bool operator==(modll x) const { return (this->modvalue == x.modvalue); } template bool operator==(A x) const { return (this->modvalue == x); } bool operator<(modll x) const { return (this->modvalue < x.modvalue); } template bool operator<(A x) const { return (this->modvalue < x); } bool operator>(modll x) const { return (this->modvalue > x.modvalue); } template bool operator>(A x) { return (this->modvalue > x); } bool operator<=(modll x) const { return (this->modvalue <= x.modvalue); } template bool operator<=(A x) const { return (this->modvalue <= x); } bool operator>=(modll x) const { return (this->modvalue >= x.modvalue); } template bool operator>=(A x) const { return (this->modvalue >= x); } void operator+=(const modll &x) { this->modvalue += x.modvalue; this->modvalue %= mod; } template void operator+=(A x) { if (x < 0) this->operator+=(-1 * x); this->modvalue += x%mod; if (modvalue < 0) { this->modvalue *= -1; if (modvalue%mod == 0) modvalue = 0; else modvalue = mod-(modvalue % mod); } this->modvalue %= mod; } void operator-=(const modll &x) { this->modvalue -= x.modvalue; while (this->modvalue < 0) this->modvalue += mod; this->modvalue %= mod; } template void operator-=(A x) { if (x < 0) this->operator+=(-1 * x); this->modvalue -= x % mod; if (modvalue < 0) { this->modvalue *= -1; if (modvalue%mod == 0) modvalue = 0; else modvalue = mod - (modvalue % mod); } this->modvalue %= mod; } void operator*=(const modll &x) { this->modvalue *= x.modvalue; this->modvalue %= mod; } template void operator*=(A x) { bool neg = false; if (x < 0) { neg = true; x *= -1; } this->modvalue *= x % mod; if (modvalue < 0) { this->modvalue *= -1; if (modvalue%mod == 0) modvalue = 0; else modvalue = mod - (modvalue % mod); } this->modvalue %= mod; if (neg) { this->modvalue = mod - modvalue; this->modvalue %= mod; } } void operator/=(const modll &x) { if (x.modvalue == 0) { this->modvalue = 0; return; } this->modvalue = this->modvalue/x.modvalue; this->modvalue %= mod; } template void operator/=(A x) { bool neg = false; if (x < 0) { neg = true; x *= -1; } modll se = x%mod; this->operator/=(se); if (modvalue < 0) { this->modvalue *= -1; if (modvalue%mod == 0) modvalue = 0; else modvalue = mod - (modvalue % mod); } this->modvalue %= mod; if (neg) { this->modvalue = mod - modvalue; this->modvalue %= mod; } } modll operator++() { modvalue++; if (modvalue==mod) modvalue=0; } modll operator--() { modvalue--; if (modvalue<0) modvalue+=mod; } void print() const { std::cout << this->modvalue; } void printspace() const { std::cout << this->modvalue << " "; } void printendl() const { std::cout << this->modvalue <v[105]; ll rc[105]; ll l[105]; ll attacked; ll n, m, k; mypriority_queue>pq; myqueueq; myvectore[105]; bool used[105]; bool usedb[105]; ll a[105]; ll p[105]; ll defendedb[105]; ll cnt; ll ans; ll cc[105]; myvectord; ll defenders; myvectorpath; bool defended[105]; ll defendcnt[105]; void dfs(ll z) { used[z]=true; for (auto s: e[z]) { if (!used[s]) { p[s]=z; ++a[z]; l[s]=l[z]+1; dfs(s); } } } bool dfs2(ll z) { used[z]=true; if (z==attacked) { path.push_back(z); return true; } for (auto s: e[z]) { if (!used[s] && (s==attacked || defended[s])) { if (dfs2(s)) { path.push_back(z); return true; } } } return false; } int main() { std::ios_base::sync_with_stdio(false); cin>>n>>m; for (int i=0; i>uu>>vv; e[uu].push_back(vv); e[vv].push_back(uu); } p[0]=0; dfs(0); for (int i=0; i1) { ++ans; } } ++ans; /* cout<=ans) { cout<<"DEFEND"<1) { d.push_back(i); defended[i]=true; } } for (int i=0; i>attacked; if (attacked==-1) { return 0; } if (defended[attacked]) { cout<<0<0; --i) { cout<ww; ww.push_back(p[i]); for (auto s: e[p[i]]) { if (s!=p[p[i]]) { if (!usedb[s]) { usedb[s]=true; ww.push_back(s); } else{ ll idx=(-1); for (int j=0; j=0) { if (v[idx].size()>2) { con=true; con_to=idx; } } } } } if (con) { ll idx=con_to; v[idx].push_to(rc[idx], p[i]); ++rc[idx]; for (int i=1; i=ans) { cout<<"DEFEND"<>attacked; if (attacked==-1) { return 0; } if (defended[attacked]) { cout<<0<0; --i) { cout<>dd; defended[dd]=true; defendcnt[dd]+=1; } for (int day=1; day<=365; ++day) { /* while (day>=365) { bool bad=true; } */ for (int i=0; iw; for (int i=0; i=n) { bool messedUp=true; } cout<>k; for (int i=0; i>uu>>vv; --cc[uu]; ++cc[vv]; } for (int i=0; i0) defended[i]=true; } ll cntd=0; for (int i=0; i