AGC004
A
有一个$a\times b\times c$个正方体堆成的长方体，要求切成两个长方体，使得不存在一个正方体被切开，并使得两边正方体个数差最小。
如果$a,b,c$是偶数则答案为0.
否则为$\min(ab,bc,ac)$。
B
Snuke想得到$n$个颜色的史莱姆各一只。
为了得到这些史莱姆，Snuke可以进行两种操作：
- 抓一个$i$颜色的史莱姆，代价$a_i$。
- 用一个膜法，把所有$i$色史莱姆变成$i+1$色，$n$色史莱姆变成1色，代价$x$
求最少代价。
枚举用膜法的次数$m$，
令$a_{i+n}=a_i$，则最终获得$i$色史莱姆的最小代价是$\min(a_{i-m},\dots a_i)$
直接计算即可。
C
有一个$W\times H$的方格纸，Snuke在上面画了一个红色的联通块，Ciel在上面画了一个蓝色的联通块。红色和蓝色加在一起会变成紫色。
告诉你哪些块是紫色，求Snuke和Ciel的一种画的方案使得最后得到的紫色块恰好是这些。
保证最外面一圈不是紫色。
首先先构造一个基础方案，使得无紫色方案，并且所有可能紫色的格子都和红色蓝色分别联通。
那就第一行涂红色，最后一行涂蓝色，然后中间奇数列红色偶数列蓝色！
然后紫色的？直接涂上两个颜色啊
显然这个是对的。
D
一个国家有$n$个城市，其中1号是首都。
每个城市有一个传送门，第$i$个城市的传送门可以从i城市传送到$a_i$城市（$a_i$可以$=i$），保证所有城市都能经过一次或多次传送到达首都。
国王Snuke喜欢一个数字$k$，他自私地希望修改一个传送门的$a_i$，使得每个城市传送$k$次的时候都在首都。
求最少修改的传送门数。
（首都也有传送门）
如果$1$ $k$次 可以到达1，则$a_1$ $k$次会到达$a_1$。所以显然$a_1=1$。
然后就得到了一棵以1为根的树，然后要求修改最少点的父亲使得每个点的深度$\le k$。
一个经典的贪心：每次选出最深的点把它的$k-1$级祖先的祖先改成1。
E
一个$W\times H$的网格，其中有一个出口，有一些位置是机器人。
每次你可以命令所有机器人全部向上/下/左/右移动一个单位，然后一个机器人到达出口的时候就被你救出来了，到网格外面就爆炸，你就不可能救出来了。
求最多救出的机器人个数。
DP，设$f_{a,b,c,d}$表示最多右移a个单位，左移b个，上移c个，下移d个最多救出来的机器人个数。
转移的时候从$f_{a-1,b,c,d},f_{a,b-1,c,d},f_{a,b,c-1,d},f_{a,b,c,d-1}$转移过来。
F
你有一个$n$点$m$边的简单联通图（$n-1\le m\le n$）。起初每个点都是白色，你每次可以将两端同色的一条边两端同时反色，求使所有点变成黑色的最小操作数。
就是说可能是树或基环树。
树
树是一个二分图。
假设在树上深度为奇数的点上放一个硬币。
那么原来的两端同色的一条边反色，就相当于把一个硬币移到相邻没有硬币的点。
假设硬币是1，空点是-1，那么每个点对答案的贡献就是它子树和的绝对值。
为什么？
因为要想子树中每个点状态翻转，必须硬币数量和空点数量是一样的。
如果多了硬币，就可以在子树根处移出去。如果少了硬币，就可以从外面移到子树根，所以子树根对外的最少操作数就是子树和的绝对值，显然这个下限是可以取到的。
环是奇环
取出奇环上一条边，则剩下的还是一棵树。
显然在这条边上操作，相当于加上两个硬币或去掉两个硬币。
那么就可以算出这条边需要的操作次数，然后就和树一样了。
环是偶环
取出偶环上一条边$a\rightarrow b$，则剩下的还是一棵树。
假设树上$b$是$a$的祖先
设$a$给了$b$ $x$个硬币（x可以为负）
则$a$到$b$的路径（不包含b）外点子树和不变，路径上点子树和加$x$
然后就是要使$|x|+\sum |x-a_i|$最小。
显然$x$就是$a_i$和0取中位数。
Code
A
/*
Author: QAQ-Automaton
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int main(){
#ifdef QAQAutoMaton
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
ll a,b,c;
read(a,b,c);
if(a&1 && b&1 && c&1){
write(min(a*b,min(a*c,b*c)),'\n');
}
else write("0\n");
return 0;
}
B
/*
Author: QAQ-Automaton
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll a[2005],f[2005],x,c,ans;
int main(){
#ifdef QAQAutoMaton
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
ll n;
read(n,x);
for(ll i=1;i<=n;++i){read(a[i]);f[i]=a[i];}
ans=(ll)1e18;
for(ll i=0;i<n;++i){
c=i*x;
for(ll j=1;j<=n;++j)c+=f[j];
chkmin(ans,c);
for(ll j=1;j<=n;++j)chkmin(f[j],a[(i+j)%n+1]);
}
write(ans,'\n');
return 0;
}C
/*
Author: QAQ-Automaton
LANG: C++
PROG: c.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
while((x=gc())==' '||x=='\n'||x=='\r');
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int r[505][505],b[505][505];
int main(){
#ifdef QAQAutoMaton
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
int n,m;
read(n,m);
char c;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
r[i][j]=(i!=n) && ((i==1)||(j&1));
b[i][j]=(i!=1) && ((i==n)||(!(j&1)));
read(c);
if(c=='#')r[i][j]=b[i][j]=1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)write(r[i][j]?'#':'.');
write('\n');
}
write('\n');
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)write(b[i][j]?'#':'.');
write('\n');
}
return 0;
}D
/*
Author: QAQ-Automaton
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int n,k;
int to[100005],dis[100005],c,ans;
vector<int> son[100005];
int q[100005],del[100005];
int work(int x){
if(x==1)return 0;
if(dis[x])return dis[x];
dis[x]=work(to[x])+1;
return dis[x];
}
int u1(){
ans=to[1]!=1;
for(int i=2;i<=n;++i)work(i);
return ans;
}
void remove(int x){
if(del[x])return;
del[x]=1;
for(auto i:son[x])remove(i);
}
int main(){
#ifdef QAQAutoMaton
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
read(n,k);
--k;
for(int i=1;i<=n;++i)read(to[i]);
ans=to[1]!=1;
to[1]=1;
for(int i=2;i<=n;++i){son[to[i]].push_back(i);work(i);q[i]=i;}
sort(q+2,q+n+1,cmp_a<dis>);
for(int *l=q+2,*r=q+n,x;l<=r;--r){
if(dis[*r]<=k+1)break;
if(del[*r])continue;
x=*r;
for(int i=k;i;--i)x=to[x];
remove(x);
++ans;
}
write(ans,'\n');
return 0;
}
E
/*
Author: QAQ-Automaton
LANG: C++
PROG: e.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
while((x=gc())=='\n' || x==' '||x=='\r');
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[105][105],f[2][105][105][105],b[105][105];
int main(){
#ifdef QAQAutoMaton
freopen("e.in","r",stdin);
freopen("e.out","w",stdout);
#endif
int n,m,x,y;
char c;
read(n,m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
read(c);
if(c=='E')x=i,y=j;
a[i][j]=c=='o';
b[i][j]=c=='o';
a[i][j]+=a[i][j-1];
b[i][j]+=b[i-1][j];
}
int ans=0;
for(int xl=0,t=0;xl<x;++xl,t^=1){
for(int xr=0;xr<=n-x;++xr){
for(int yl=0;yl<y;++yl){
for(int yr=0;yr<=m-y;++yr){
f[t][xr][yl][yr]=0;
if(xl)
chkmax(f[t][xr][yl][yr],
f[t^1][xr][yl][yr]+
(xr>=x-xl?0:max(0,a[x-xl][min(y+yr,m-yl)]-a[x-xl][max(y-yl-1,yr)]))
);
if(xr)
chkmax(f[t][xr][yl][yr],
f[t][xr-1][yl][yr]+
(xl+xr>n-x?0:max(0,a[x+xr][min(y+yr,m-yl)]-a[x+xr][max(y-yl-1,yr)]))
);
if(yl)
chkmax(f[t][xr][yl][yr],
f[t][xr][yl-1][yr]+
(yl+yr>=y?0:max(0,b[min(x+xr,n-xl)][y-yl]-b[max(x-xl-1,xr)][y-yl]))
);
if(yr)
chkmax(f[t][xr][yl][yr],
f[t][xr][yl][yr-1]+
(yl+yr>m-y?0:max(0,b[min(x+xr,n-xl)][y+yr]-b[max(x-xl-1,xr)][y+yr]))
);
chkmax(ans,f[t][xr][yl][yr]);
}
}
}
}
write(ans,'\n');
return 0;
}F
/*
Author: QAQ-Automaton
LANG: C++
PROG: f.cpp
Mail: cnyalilk@vip.qq.com */
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll inf=1e12;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
*x=0;
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll f[100005][2],tag[100005],OddCircle;
ll cnt[100005];
vector<ll> son[100005],QAQ[100005];
void dfs(ll x,ll flg){
if(tag[x]){if(tag[x]!=flg)OddCircle=1;return;}
tag[x]=flg;
for(auto i:son[x])dfs(i,-flg);
}
ll vis[100005],fa[100005];
void dfs2(ll x,ll fa){
vis[x]=1;
cnt[x]=tag[x];
for(auto i:son[x])if(i!=fa && !vis[i]){
dfs2(i,x);
cnt[x]+=cnt[i];
}
}
namespace Tree{
void main(ll n){
dfs2(1,0);
if(cnt[1]){write("-1\n");return;}
ll ans=0;
for(ll i=1;i<=n;++i)ans+=abs(cnt[i]);
write(ans,'\n');
}
}
pii E;
void gete(ll x,ll f){
fa[x]=f;
vis[x]=1;
cnt[x]=tag[x];
for(auto i:son[x])if(i!=f){
if(!vis[i]){
gete(i,x);
cnt[x]+=cnt[i];
}
else{
E=make_pair(x,i);
}
}
}
namespace Odd{
void main(ll n){
gete(1,0);
if(cnt[1]%2){write("-1\n");return;}
tag[E.x]-=cnt[1]>>1;
tag[E.y]-=cnt[1]>>1;
ll ans=abs(cnt[1]>>1);
for(ll i=1;i<=n;++i)vis[i]=0;
dfs2(1,0);
for(ll i=1;i<=n;++i)ans+=abs(cnt[i]);
write(ans,'\n');
}
}
namespace Even{
ll a[100005];
void main(ll n){
gete(1,0);
if(cnt[1]){write("-1\n");return;}
for(ll i=1;i<=n;++i)vis[i]=0;
ll ans=0,t=0;
for(ll i=1;i<=n;++i)ans+=abs(cnt[i]);
ll u=E.x,v=E.y;
for(;u&&u!=v;u=fa[u]);
if(u==v)u=E.x;
else{
u=E.y;
v=E.x;
}
for(;u!=v;u=fa[u]){
ans-=abs(cnt[u]);
a[++t]=cnt[u];
}
a[++t]=0;
sort(a+1,a+t+1);
ll mid=(t+1)>>1;
for(ll i=1;i<=t;++i)ans+=abs(a[i]-a[mid]);
write(ans,'\n');
}
}
int main(){
#ifdef QAQAutoMaton
freopen("f.in","r",stdin);
freopen("f.out","w",stdout);
#endif
ll n,m,u,v;
read(n,m);
for(;m;--m){
read(u,v);
son[u].push_back(v);
son[v].push_back(u);
}
dfs(1,1);
if(n==m+1)Tree::main(n);
else if(OddCircle)Odd::main(n);
else Even::main(n);
return 0;
}