/*#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
ifstream fin("fibosnek.in");
ofstream fout("fibosnek.out");
int c, n, m, maxy = 1, nr = 0;
vector<int> v;
set<int> S;
void read()
{
int i, j;
for (i = 0;i < n;i++)
for (j = 0;j < m;j++)
{
fin >> v[i + j * n];
if (maxy < v[i + j * n])
maxy = v[i + j * n];
}
}
void fibosnek()
{
S.insert(1);
int x = 1, y = 1, t, j;
while (x + y <= maxy)
{
S.insert(x + y);
t = x;
x += y;
y = t;
}
}
void solve1()
{
int i, j;
for (i = 0;i < n * m;i++)
if (S.find(v[i]) != S.end())
nr++;
fout << nr;
}
void fibo(int& x)
{
int q = 1, y = 1, t, i, j;
bool ok = 0;
for (i = 0;!ok;i++)
{
if (x > q and x < y)
if (x - q <= y - x)
{
x = q;
ok = 1;
}
else
{
x = y;
ok = 1;
}
t = q;
q = y;
y = q + t;
}
}
void solve2()
{
int s = 0, t, i, sol = 0, l = 0, j, L = 0, k;
bool ok;
for (i = 0;i < n * m;i++)
if (S.find(v[i]) == S.end())
{
s = 0;
k = i;
t = v[i];
fibo(t);
s += t;
ok = 1;
for (j = i - 1;j >= 0 and ok;j--)
if (S.find(v[j]) != S.end())
s += v[j];
else
ok = 0;
if (ok == 1)
l += i;
else
l += i - j + 1;
ok = 1;
for (j = i + 1;j < n * m and ok;j++)
if (S.find(v[j]) != S.end())
s += v[j];
else
if (S.find(v[j - 1]) == S.end())
{
t = v[j];
fibo(t);
s += t;
k = j;
}
else
ok = 0;
if (ok == 1)
l += n * m - k;
else
l += j - k;
if (L < l)
{
L = l;
sol = s;
}
l = 0;
i = k;
}
fout << sol;
}
int main()
{
fin >> c >> n >> m;
v.resize(n * m);
read();
fibosnek();
if (c == 1)
solve1();
else
solve2();
}*/
/*#include<iostream>
#include<fstream>
#include<stack>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
string text;
ifstream fin("expresie.in");
ofstream fout("expresie.out");
short x;
vector<int> v;
stack<int> S;
int i = 0, nr = 0, s, smax;
getline(fin, text);
while (i < text.length())
if (text[i] == '(')
{
S.push(-10000);
i++;
}
else
if (text[i] == '[')
{
S.push(-10001);
i++;
}
else
if (text[i] == ',')
{
nr++;
i++;
}
else
if (text[i] == '-')
{
i++;
x = 0;
while (isdigit(text[i]))
{
x = x * 10 + (text[i] - '0');
i++;
}
S.push(x * (-1));
}
else
if (isdigit(text[i]))
{
x = 0;
while (isdigit(text[i]))
{
x = x * 10 + (text[i] - '0');
i++;
}
S.push(x);
}
else
if (text[i] == ')')
{
s = S.top();
smax = s;
S.pop();
while (S.top() != -10000)
{
s += S.top();
if (s < S.top())
s = S.top();
if (s > smax)
smax = s;
S.pop();
}
S.pop();
S.push(smax);
i++;
}
else
if (text[i] == ']')
{
v.clear();
while (S.top() != -10001)
{
v.push_back(S.top());
S.pop();
}
sort(v.begin(), v.end());
S.pop();
S.push(v[(v.size() - 1) / 2]);
i++;
}
s = 0;
while (!S.empty())
{
s += S.top();
S.pop();
}
fout << nr + 1 << '\n' << s;
}*/
//Backtracking
/*#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> v;
vector<bool> folosit;
void Bckt(int k)
{
if (k == n + 1)
{
for (int i = 1;i <= n;i++)
cout << v[i] << " ";
cout << endl;
}
else
for (int i = 1;i <= n;i++)
{
v[k] = i;
if (folosit[i] == false)
{
folosit[i] = true;
Bckt(k + 1);
folosit[i] = false;
}
}
}
int main()
{
cin >> n;
v.resize(n + 1);
folosit.resize(n + 1);
Bckt(1);
}*/
/*#include<iostream>
#include<vector>
using namespace std;
int n, m;
vector<int> v;
void Bckt(int k)
{
if (k == m + 1)
{
for (int i = 1;i <= m;i++)
cout << v[i] << " ";
cout << endl;
}
else
for (int i = v[k - 1] + 1;i <= n;i++)
{
v[k] = i;
Bckt(k + 1);
}
}
int main()
{
cin >> n >> m;
v.resize(m + 1);
Bckt(1);
}*/
/*#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
ifstream fin("fraze.in");
ofstream fout("fraze.out");
int main()
{
map<char, int> M;
string text;
vector<string> v;
int i, sz, nr = 0, pf, nrpf = 0;
while (getline(fin, text))
{
M.clear();
sz = text.size();
pf = 1;
for (i = 0;i < sz;i++)
if (islower(text[i]) or isupper(text[i]))
{
M[tolower(text[i])]++;
if (M[tolower(text[i])] > 1)
pf = 0;
}
if (M.size() == 26)
{
nr++;
if (pf)
nrpf++;
v.push_back(text);
}
}
fout << nr << " " << nrpf << endl;
sort(v.begin(), v.end());
sz = v.size();
for (i = 0;i < sz;i++)
fout << v[i] << endl;
}*/
/*#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> v;
vector<bool> folosit;
void Bckt(int k)
{
if (k == n + 1)
{
for (int i = 1;i <= n;i++)
cout << v[i] << " ";
cout << endl;
}
else
for (int i = 1;i <= n;i++)
{
v[k] = i;
if (folosit[i] == false)
{
folosit[i] = true;
Bckt(k + 1);
folosit[i] = false;
}
}
}
int main()
{
cin >> n;
v.resize(n + 1);
folosit.resize(n + 1);
Bckt(1);
}*/
/*#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n, i;
cin >> n;
vector<int> v(n), x(n);
for (i = 0;i < n;i++)
{
cin >> x[i];
v[i] = i;
}
do
{
for (i = 0;i < n;i++)
cout << x[v[i]] << " ";
cout << endl;
} while (next_permutation(v.begin(), v.end()));
}*/
/*#include<iostream>
#include<vector>
using namespace std;
vector<int> x = { 12,4,5,15 }, v;
int n, m;
void comb(int k)
{
if (k == m + 1)
{
for (int i = 1;i <= m;i++)
cout << x[v[i] - 1] << " ";
cout << endl;
}
else
for (int i = v[k - 1] + 1;i <= n;i++)
{
v[k] = i;
comb(k + 1);
}
}
int main()
{
n = x.size();
cin >> m;
v.resize(m + 1);
comb(1);
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream fin("pluricex.in");
ofstream fout("pluricex.out");
int d, n, k;
vector<int> v;
vector<vector<int> > M;
set<int> S;
void sol()
{
S.clear();
for (int i = 1;i <= k;i++)
for (auto t : M[v[i]])
S.insert(t);
if (S.size() == d)
{
for (int i = 1;i <= k;i++)
fout << v[i] << " ";
fout << '\n';
}
}
void Comb(int p)
{
if (p == k + 1)
{
sol();
}
else
for (int i = v[p - 1] + 1;i <= n;i++)
{
v[p] = i;
Comb(p + 1);
}
}
int main()
{
int t, y;
fin >> n >> k >> d;
vector<int> x;
x.push_back(0);
M.push_back(x);
for (int i = 1;i <= n;i++)
{
fin >> t;
x.clear();
for (int j = 1;j <= t;j++)
{
fin >> y;
x.push_back(y);
}
M.push_back(x);
}
v.resize(d + 1);
Comb(1);
}*/
/*#include<iostream>
#include<string>
using namespace std;
int main()
{
string text;
getline(cin, text);
int i = 0;
while (i < text.size())
{
if (text[i] == '-')
{
text.erase(i, 1);
while (isdigit(text[i]) or text[i] == ',')
text.erase(i, 1);
}
else
i++;
}
cout << text;
}*/
/*#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
char x[100];
cin.getline(x, 100);
int i = 0;
while (i < strlen(x))
{
if (x[i] == '-')
{
strcpy(x + i, x + i + 1);
while (isdigit(x[i]) or x[i] == ',')
strcpy(x + i, x + i + 1);
}
else
i++;
}
cout << x;
}*/
/*#include<iostream>
#include<string>
using namespace std;
int main()
{
string text, cuvant;
getline(cin, text);
text += " ";
int i = 0, first = 0, last;
while (i < text.length())
{
if (text[i] == ' ')
{
last = i;
cuvant = text.substr(first, last - first);
first = i + 1;
cout << cuvant << endl;
}
i++;
}
}*/
//Divide et impera
/*#include<iostream>
using namespace std;
void DEI(int st, int dr)
{
int m = (st + dr) / 2;
if (st < dr)
{
cout << m << " ";
DEI(st, m);
DEI(m + 1, dr);
}
}
int DEI1(int st, int dr)
{
int m = (st + dr) / 2;
if (st == dr)
return m;
else
return DEI1(st, m) + DEI1(m + 1, dr);
}
int main()
{
int n;
cin >> n;
cout << DEI1(1, n) << " ";
}*/
/*#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> v;
void Citire()
{
int i;
cin >> n;
v.resize(n);
for (i = 0; i < n; i++)
cin >> v[i];
}
int DEI_suma(int st, int dr)
{
int m = (st + dr) / 2;
if (st == dr)
return v[m];
else
return DEI_suma(st, m) + DEI_suma(m + 1, dr);
}
int DEI_max(int st, int dr)
{
int m = (st + dr) / 2, m1, m2;
if (st == dr)
return v[m];
else
{
m1 = DEI_max(st, m);
m2 = DEI_max(m + 1, dr);
if (m1 > m2)
return m1;
else
return m2;
}
}
int DEI_prpar(int st, int dr)
{
int m = (st + dr) / 2;
if (st == dr)
{
if (v[m] % 2 == 0)
return v[m];
else
return 1;
}
else
return DEI_prpar(st, m) * DEI_prpar(m + 1, dr);
}
bool DEI_binary(int st, int dr, int x)
{
int m = (st + dr) / 2;
if (st > dr)
return 0;
else
if (v[m] == x)
return 1;
else
if (x < v[m])
return DEI_binary(st, m - 1, x);
else
return DEI_binary(m + 1, dr, x);
}
int main()
{
Citire();
sort(v.begin(), v.end());
int x;
cin >> x;
cout << DEI_binary(0, n - 1, x);
}*/
//Suma si produs
/*#include<iostream>
#include<string>
#include<vector>
using namespace std;
void suma(string a, string b, string& s)
{
int la = a.length(), lb = b.length();
int t = max(la, lb) + 1;
int minte = 0;
vector<int> va(t, 0), vb(t, 0), suma(t, 0);
for (int i = la - 1;i >= 0;i--)
va[la - i - 1] = a[i] - '0';
for (int i = lb - 1;i >= 0;i--)
vb[lb - i - 1] = b[i] - '0';
for (int i = 0;i < t;i++)
{
int sm = va[i] + vb[i] + minte;
suma[i] = sm % 10;
minte = sm / 10;
}
if (suma[t - 1] == 0)
{
t--;
suma.pop_back();
}
for (int i = t - 1;i >= 0;i--)
s.push_back(suma[i] + '0');
}
int main()
{
string a, b, s;
getline(cin, a);
getline(cin, b);
suma(a, b, s);
cout << s;
}*/
/*#include<iostream>
#include<string>
#include<vector>
using namespace std;
void prod_cifra(string a, short c)
{
int la = a.length();
vector<int> va(la + 1, 0), p(la + 1, 0);
int minte = 0, i;
for (i = la - 1;i >= 0;i--)
va[la - i - 1] = a[i] - '0';
for (i = 0;i <= la;i++)
{
int s = minte + va[i] * c;
p[i] = s % 10;
minte = s / 10;
}
if (p[la] == 0)
{
p.pop_back();
la--;
}
for (i = la;i >= 0;i--)
cout << p[i];
}
int main()
{
string a;
short c;
getline(cin, a);
cin >> c;
prod_cifra(a, c);
}*/
/*#include<iostream>
#include<string>
#include<vector>
using namespace std;
void produs(string a, string b, string& c)
{
int la = a.length(), lb = b.length();
int t = la + lb;
int minte = 0;
vector<int> va(t, 0), vb(t, 0), p(t, 0);
for (int i = la - 1;i >= 0;i--)
va[la - i - 1] = a[i] - '0';
for (int i = lb - 1;i >= 0;i--)
vb[lb - i - 1] = b[i] - '0';
for (int i = 0;i < la;i++)
for (int j = 0;j < lb;j++)
p[i + j] += va[i] * vb[j];
for (int i = 0;i < t;i++)
{
int s = minte + p[i];
p[i] = s % 10;
minte = s / 10;
}
if (p[t - 1] == 0)
{
t--;
p.pop_back();
}
for (int i = t - 1;i >= 0;i--)
cout << p[i];
}
int main()
{
string a, b, c;
getline(cin, a);
getline(cin, b);
produs(a, b, c);
}*/
//Impartire
/*#include<iostream>
#include<string>
#include<vector>
using namespace std;
int rest(string& a, int b)
{
int la = a.size(), r = 0;
vector<int> A(la + 1), rez;
for (int i = 0;i < la;i++)
A[i] = a[i] - '0';
for (int i = 0;i < la;i++)
{
r = r * 10 + A[i];
rez.push_back(r / b);
r %= b;
}
while (rez[0] == 0)
rez.erase(rez.begin());
int rsz = rez.size();
for (int i = 0;i < rsz;i++)
cout << rez[i];
cout << endl;
return r;
}
int main()
{
string a;
int b;
getline(cin, a);
cin >> b;
cout << rest(a, b);
}*/
//Aritmetica modulara
/*#define MOD 100007
#include<iostream>
using namespace std;
int main()
{
int n, sum = 0;
cin >> n;
for (int i = 1;i <= n;i++)
sum = (sum + i) % MOD;
cout << sum;
}*/
/*#include<iostream>
using namespace std;
#define MOD 100007
int main()
{
unsigned long long n;
int p = 1;
cin >> n;
for (unsigned long long i = 1;i <= n;i++)
p = (p * i) % MOD;
cout << p;
}*/
/*#include<iostream>
using namespace std;
#define MOD 2000005
int main()
{
unsigned long long a, b;
cin >> a >> b;
int s = 0;
for (unsigned long long i = 1;i <= a;i++)
s = (s + b) % MOD;
cout << s;
}*/
/*#include<iostream>
using namespace std;
#define MOD 300007
int main()
{
unsigned long long n, m;
cin >> n >> m;
int p = 1;
for (unsigned long long i = 1;i <= n;i++)
p = (p * m) % MOD;
cout << p;
}*/
//Arnjamente de n liate de cate m
/*#include <iostream>
using namespace std;
#define MOD 300007
int main()
{
long long int n, m, p = 1;
cin >> n >> m;
for (long long int i = n - m + 1; i <= n; ++i)
p = (p * i) % MOD;
cout << p << '\n';
}*/
//Combinari de n luate cate m
/*#include<iostream>
#include<vector>
using namespace std;
#define MOD 300007
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> Pascal(n + 1);
for (int i = 0;i <= n;i++)
Pascal[i].resize(i + 1);
Pascal[0][0] = 1;
for (int i = 1;i <= n;i++)
{
Pascal[i][0] = 1;
Pascal[i][i] = 1;
for (int j = 1;j < i;j++)
Pascal[i][j] = (Pascal[i - 1][j] + Pascal[i - 1][j - 1]) % MOD;
}
cout << Pascal[n][m];
}*/
/*#include<iostream>
#include<fstream>
#include<string>
using namespace std;
ifstream fin("caps.in");
ofstream fout("caps.out");
string next(string text)
{
int sz = text.size();
for (int i = 0;i < sz;i++)
if (islower(text[i]))
text[i] = toupper(text[i]);
else
text[i] = tolower(text[i]);
return text;
}
int main()
{
int k, q, c, nr;
fin >> k >> q;
fin.get();
string text;
getline(fin, text);
for (int i = 1;i <= q;i++)
{
nr = 0;
fin >> c;
c--;
while (text.size() < c)
text += next(text);
fout << text[c] << " ";
for (int j = 0;j <= c;j++)
if (text[j] == text[c])
nr++;
fout << nr << endl;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("rover.in");
ofstream fout("rover.out");
int n, g;
vector<vector<int>> M, K;
void rsz()
{
M.resize(n + 2);
K.resize(n + 2);
for (int i = 0;i <= n + 1;i++)
M[i].resize(n + 2);
for (int i = 0;i <= n + 1;i++)
K[i].resize(n + 2);
}
void board()
{
for (int i = 0;i <= n + 1;i++)
K[i][0] = K[i][n + 1] = -1;
for (int j = 0;j <= n + 1;j++)
K[0][j] = K[n + 1][j] = -1;
}
void print()
{
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= n;j++)
cout << K[i][j] << " ";
cout << endl;
}
}
void read()
{
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
fin >> M[i][j];
}
void Lee()
{
queue<pair<int, int>> Q;
pair<int, int> element;
vector<int> di = { 1,0,0,-1 };
vector<int> dj = { 0,1,-1,0 };
Q.push({ 1,1 });
int val = 1;
K[1][1] = 1;
while (!Q.empty() and K[n][n] == 0)
{
element = Q.front();
Q.pop();
val++;
for (int i = 0;i <= 3;i++)
if (K[element.first + di[i]][element.second + dj[i]] == 0)
{
K[element.first + di[i]][element.second + dj[i]] = val;
Q.push({ element.first + di[i],element.second + dj[i] });
}
}
}
int main()
{
int v;
fin >> v;
fin >> n;
rsz();
board();
if (v == 1)
{
fin >> g;
read();
Lee();
print();
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("sir.in");
ofstream fout("sir.out");
vector<int> v;
int nr = 0;
bool vf(int n)
{
int val = v[0];
for (int i = 1;i < n;i++)
if (val != v[i])
return 1;
return 0;
}
void Bkt(int n, int x, int k)
{
if (k == n - 1)
{
if (vf(n))
nr++;
}
else
for (int i = 1;i < x;i++)
{
v[k] = i;
Bkt(n, x, k + 1);
}
}
int main()
{
int p, n, x;
fin >> p >> n >> x;
v.resize(n);
v[0] = 1;
v[n - 2] = x;
if (p == 1)
{
Bkt(n, x, 0);
fout << nr;
}
}*/
//Exponentiere rapida
/*#include<iostream>
using namespace std;
#define ull unsigned long long
ull putere(int a, int exp)
{
ull p = 1;
while (exp)
if (exp % 2 == 1)
{
p *= a;
exp--;
}
else
{
a *= a;
exp /= 2;
}
return p;
}
int main()
{
int a, exp;
cin >> a >> exp;
cout << putere(a, exp);
}*/
/*#include<iostream>
using namespace std;
#define ull unsigned long long
#define MOD 1000000007
ull putere(int a, int exp)
{
ull p = 1;
while (exp)
{
if (exp % 2 == 1)
p *= a;
exp /= 2;
a *= a;
}
return p;
}
int main()
{
int a, exp;
cin >> a >> exp;
cout << putere(a, exp);
}*/
/*#include<iostream>
using namespace std;
#define ull unsigned long long
#define MOD 1000000007
ull putere(int a, int exp)
{
ull p = 1;
while (exp)
{
if (exp % 2 == 1)
p = (p * a) % MOD;
exp /= 2;
a = (a * a) % MOD;
}
return p;
}
int main()
{
int a, exp;
cin >> a >> exp;
cout << putere(a, exp);
}*/
/*#include<iostream>
#include<climits>
using namespace std;
#define MOD 1000000007
int putere(int x, int y)
{
int p = 1;
while (y)
{
if (y % 2 == 1)
p = (p * x) % MOD;
y /= 2;
x = (x * x) % MOD;
}
return p;
}
int main()
{
int a, b, c;
cin >> a >> b >> c;
cout << putere(a, putere(b, c));
}*/
//Algoritmul lui Euclid
/*#include<iostream>
using namespace std;
void Cmmdc(int a, int b, int& c)
{
if (b == 0)
c = a;
else
Cmmdc(b, a % b, c);
}
int main()
{
int c;
Cmmdc(242, 2000002, c);
cout << c;
}*/
/*#include<iostream>
using namespace std;
void Cmmdc_ext(int a, int b, int& c, int& x, int& y)
{
int x1, y1;
if (b == 0)
{
c = a;
x = 1;
y = 1;
}
else
{
Cmmdc_ext(b, a % b, c, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
}
}
int main()
{
int a, b, c, x, y;
cin >> a >> b;
Cmmdc_ext(a, b, c, x, y);
cout << x << " " << y;
}*/
//Invers modular
/*#include<iostream>
using namespace std;
void Cmmdc_ext(int a, int MOD, int& x, int& y)
{
int x1, y1;
if (MOD == 0)
{
x = 1;
y = 1;
}
else
{
Cmmdc_ext(MOD, a % MOD, x1, y1);
x = y1;
y = x1 - (a / MOD) * y1;
}
}
int main()
{
int a, MOD, x, y;
cin >> a >> MOD;
Cmmdc_ext(a, MOD, x, y);
while (x < 0)
x += MOD;
cout << x;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
#define MOD 1000000007
ifstream fin("dorel.in");
ofstream fout("dorel.out");
int C(int b, int c)
{
int nr = 0;
vector<int> v(c);
for (int i = c - 1;i >= 0 and b;i--)
{
v[i] = b;
b--;
}
do
{
nr = (nr + 1) % MOD;
} while (next_permutation(v.begin(), v.end()));
return nr;
}
int main()
{
int b, c, k, t;
fin >> t;
for (int i = 0;i < t;i++)
{
fin >> b >> c >> k;
if (b > k or c > k)
fout << 0 << endl;
else
fout << C(b, c) << endl;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("egale.in");
ofstream fout("egale.out");
bool vf(int l, int r, vector<int> V)
{
for (int i = l;i < r;i++)
if (V[i] != V[i + 1])
return 0;
return 1;
}
int main()
{
int n, q;
fin >> n >> q;
vector<int> V(n + 1);
for (int i = 1;i <= n;i++)
fin >> V[i];
int l, r, v;
bool ok;
for (int i = 0;i < q;i++)
{
fin >> l >> r >> v;
ok = vf(l, r, V);
if (ok)
{
if (v == 0)
{
if (v == V[l])
fout << 0 << endl;
else
fout << 1 << endl;
}
else
if (v < V[l])
fout << v + 1 << endl;
else
fout << v - V[l] << endl;
}
else
{
if (v == 0)
fout << 1 << endl;
else
fout << v + 1 << endl;
}
}
}*/
/*#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
string solve1()
{
string text;
getline(cin, text);
int sz = text.size();
string voc = "aeiouAEIOU";
for (int i = sz - 1;i >= 0;i--)
if (voc.find(text[i]) == string::npos)
{
text.erase(i, 1);
return text;
}
return text;
}
string solve2()
{
string text1, text2, sufix;
getline(cin, text1);
getline(cin, text2);
int i = text1.size(), j = text2.size();
while (i != 0 and j != 0)
{
i--;
j--;
if (text1[i] == text2[j])
sufix.insert(0, 1, text1[i]);
else
break;
}
if (sufix.begin() != sufix.end())
return sufix;
else
return "NU EXISTA";
}
void solve4()
{
string text, word;
getline(cin, text);
int val = text.find('*');
word = text.substr(0, val);
text.erase(0, val);
val = text.find(word);
while (val != string::npos)
{
if (!islower(text[val - 1]) and !isupper(text[val - 1]))
text.erase(val, word.size());
val = text.find(word, val + 1);
}
cout << text;
}
bool Comp(pair<string, string>a, pair<string, string> b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
void name_sort()
{
vector<pair<string, string>> v(5);
string text;
int f;
for (int i = 0;i < 5;i++)
{
cin >> v[i].first >> v[i].second;
v[i].first[0] = toupper(v[i].first[0]);
}
sort(v.begin(), v.end(), Comp);
for (int i = 0;i < 5;i++)
cout << v[i].first << " " << v[i].second << endl;
}
void solve5()
{
string text, word;
getline(cin, text);
int sz = text.length();
for (int i = 0;i < sz;i++)
{
word = text;
word.erase(i, 1);
cout << word << endl;
}
}
int main()
{
name_sort();
}*/
/*#include<iostream>
#include<fstream>
#include<set>
using namespace std;
ifstream fin("numere.in");
pair<bool, short> max_c(int n)
{
short c = 0;
while (n)
{
if (c < n % 10)
c = n % 10;
n /= 10;
}
return { c % 2 == 1,c };
}
int main()
{
int x, y;
pair<bool, short> a, b;
multiset<pair<int, short> > S;
multiset<pair<int, short> >::iterator t;
while (fin >> x >> y)
{
a = max_c(x);
b = max_c(y);
if (a.first)
S.insert({ x,a.second });
if (b.first)
S.insert({ y,b.second });
}
for (t = S.begin();t != S.end();t++)
cout << (*t).first << " " << (*t).second << endl;
}*/
/*#include<iostream>
#include<fstream>
#include<set>
using namespace std;
ifstream fin("numere.in");
bool Comp(pair<int, int> a, pair<int, int> b)
{
if (a.first == b.first)
return a.second > b.second;
return a.first > b.first;
}
int main()
{
int x, y;
multiset<pair<int, int>, bool(*)(pair<int, int>, pair<int, int>) > S(Comp);
while (fin >> x >> y)
S.insert({ x,y });
multiset<pair<int, int> >::iterator t;
for (t = S.begin();t != S.end();t++)
cout << (*t).first << " " << (*t).second << endl;
}*/
/*#include<iostream>
#include<fstream>
#include<set>
using namespace std;
ifstream fin("numere.in");
int main()
{
multiset < pair<pair<int, int>, int> > S;
multiset < pair<pair<int, int>, int> >::iterator t;
int x, y;
while (fin >> x >> y)
S.insert({ {x,y},y - x + 1 });
pair<pair<int, int>, int> w = *S.rbegin();
S.erase(*S.rbegin());
for (t = S.begin();t != S.end();t++)
if ((*t).second == w.second)
cout << (*t).first.first << " " << (*t).first.second << endl;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream fin("numere.in");
set<int> cifre(int x)
{
set<int> C;
while (x)
{
C.insert(x % 10);
x /= 10;
}
return C;
}
int main()
{
set<pair<set<int>, int> > S;
set<pair<set<int>, int> >::iterator t;
int x;
set<int> C;
while (fin >> x)
{
C = cifre(x);
S.insert({ C,x });
}
set<int> Q = {};
for (t = S.begin();t != S.end();t++)
if (Q != (*t).first)
{
Q = (*t).first;
if (t != S.begin())
cout << endl;
cout << (*t).second << " ";
}
else
cout << (*t).second << " ";
}*/
//Bkt
/*#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
vector<bool> folosit;
int n;
void Bkt(int k)
{
if (k == n + 1)
{
for (int i = 1;i <= n;i++)
cout << v[i] << " ";
cout << endl;
}
else
for (int i = 1;i <= n;i++)
{
v[k] = i;
if (folosit[i] == 0)
{
folosit[i] = 1;
Bkt(k + 1);
folosit[i] = 0;
}
}
}
int main()
{
cin >> n;
v.resize(n + 1);
folosit.resize(n + 1);
Bkt(1);
}*/
//Aranjamente
/*#include<iostream>
#include<vector>
using namespace std;
int n, m;
vector<int> v;
vector<bool> folosit;
void Prm(int k)
{
if (k == m + 1)
{
for (int i = 1;i <= m;i++)
cout << v[i] << " ";
cout << endl;
}
else
for (int i = 1;i <= n;i++)
{
v[k] = i;
if (folosit[i] == 0)
{
folosit[i] = 1;
Prm(k + 1);
folosit[i] = 0;
}
}
}
int main()
{
cin >> n >> m;
v.resize(m + 1);
folosit.resize(n + 1);
Prm(1);
}*/
//Combinari
/*#include<iostream>
#include<vector>
using namespace std;
int n, m;
vector<int> v;
void Comb(int k)
{
if (k == m + 1)
{
for (int i = 1;i <= m;i++)
cout << v[i] << " ";
cout << endl;
}
else
for (int i = v[k - 1] + 1;i <= n;i++)
{
v[k] = i;
Comb(k + 1);
}
}
int main()
{
cin >> n >> m;
v.resize(m + 1);
Comb(1);
}*/
/*#include<iostream>
#include<vector>
using namespace std;
void C(int n, int m)
{
vector<int> v1 = { 1,1 }, v2;
for (int i = 1;i <= n;i++)
{
v2 = { 1 };
for (int j = 1;j < i;j++)
v2.push_back(v1[j] + v1[j - 1]);
v2.push_back(1);
v1 = v2;
}
cout << v2[m];
}
int main()
{
int n, m;
cin >> n >> m;
C(n, m);
}*/
//Pointers
/*#include<iostream>
using namespace std;
int main()
{
int a, * p;
a = 6;
p = &a;
*p = 18;
cout << a << endl;
a = 24;
cout << *p;
}*/
/*#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
using namespace std;
int main()
{
int n, * v;
scanf("%d", &n);
v = new int[n];
for (int i = 0;i < n;i++)
scanf("%d", v + i);
for (int i = 0;i < n;i++)
printf("%d ", *(v + i));
}*/
/*#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
using namespace std;
int main()
{
int n, * v, * p;
scanf("%d", &n);
v = new int[n];
for (p = v;p - v < n;p++)
scanf("%d", p);
for (p = v;p - v < n;p++)
printf("%d ", *p);
}*/
/*#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
int* search(int* v, int n, int x)
{
int* p = v;
while (p - v < n and *p != x)
p++;
if (p - v >= n)
return NULL;
return p;
}
int main()
{
int n, * v, x;
scanf("%d", &n);
v = new int[n];
for (int* p = v;p - v < n;p++)
scanf("%d", p);
scanf("%d", &x);
if (search(v, n, x) == NULL)
printf("Nu exista");
else
printf("%d", *search(v, n, x));
}*/
/*#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
void Union(int* v, int* n, int* w, int m)
{
int* p = v + *n, * q = w;
for (int i = 0;i < m;i++)
*(p + i) = *(q + i);
*n += m;
}
int main()
{
int n, m, * v, * w;
scanf("%d", &n);
v = new int[n];
for (int* p = v;p - v < n;p++)
scanf("%d", p);
scanf("%d", &m);
w = new int[m];
for (int* p = w;p - w < m;p++)
scanf("%d", p);
Union(v, &n, w, m);
for (int* p = v;p - v < n;p++)
printf("%d ", *p);
}*/
//Liste simple inlantuite dinamic
/*#include<iostream>
using namespace std;
struct Nod
{
int val;
Nod* adr;
};
int main()
{
Nod* a, * b, * c, * d;
a = new Nod;
b = new Nod;
c = new Nod;
d = new Nod;
a->val = 5;
a->adr = b;
b->val = 1;
b->adr = c;
c->val = 8;
c->adr = d;
d->val = 10;
d->adr = NULL;
for (Nod* p = a;p;p = p->adr)
cout << p->val << " ";
}*/
/*#include<iostream>
using namespace std;
struct Nod
{
int val;
Nod* adr;
};
int main()
{
Nod* first, * last, * crt;
int n, x;
cin >> n;
first = last = 0;
for (int i = 1;i <= n;i++)
{
cin >> x;
crt = new Nod;
crt->val = x;
crt->adr = 0;
if (first == 0)
first = crt;
else
last->adr = crt;
last = crt;
}
for (Nod* p = first;p;p = p->adr)
cout << p->val << " ";
}*/
/*#include<iostream>
using namespace std;
struct NOD
{
int val;
NOD* adr;
};
int main()
{
NOD* first, * last, * crt;
int n, x;
cin >> n;
first = last = 0;
for (int i = 1;i <= n;i++)
{
cin >> x;
crt = new NOD;
crt->val = x;
crt->adr = 0;
if (!first)
first = crt;
else
last->adr = crt;
last = crt;
}
int max = first->val;
for (NOD* p = first;p;p = p->adr)
if (max < p->val)
max = p->val;
cout << max;
}*/
/*#include<iostream>
using namespace std;
struct NOD
{
int val;
NOD* adr;
};
int main()
{
NOD* first, * last, * crt;
int n, x;
cin >> n;
first = last = 0;
for (int i = 1;i <= n;i++)
{
cin >> x;
crt = new NOD;
crt->val = x;
crt->adr = 0;
if (!first)
first = crt;
else
last->adr = crt;
last = crt;
}
int nr = 0;
NOD* second = first->adr;
for (NOD* p = second;p;p = p->adr)
if (p->val == first->val)
nr++;
cout << nr;
}*/
/*#include<iostream>
using namespace std;
struct NOD
{
int val;
NOD* adr;
};
int main()
{
NOD* first, * last, * crt;
int n, x;
cin >> n;
first = last = 0;
for (int i = 1;i <= n;i++)
{
cin >> x;
crt = new NOD;
crt->val = x;
crt->adr = 0;
if (!first)
first = crt;
else
last->adr = crt;
last = crt;
}
for (NOD* p = first;p != last;p = p->adr)
if (p->val < last->val)
cout << p->val << " ";
}*/
/*#include<iostream>
using namespace std;
struct NOD
{
int val;
NOD* adr;
};
void push_back(NOD* &first, NOD* &last, int x)
{
NOD* crt;
crt = new NOD;
crt->val = x;
crt->adr = 0;
if (!first)
first = crt;
else
last->adr = crt;
last = crt;
}
void print(NOD* first)
{
for (NOD* p = first;p;p = p->adr)
cout << p->val << " ";
}
void pop_front(NOD*& first)
{
NOD* p = first;
first = first->adr;
delete p;
}
int main()
{
NOD* first, * last;
int n, x;
cin >> n;
first = last = 0;
for (int i = 1;i <= n;i++)
{
cin >> x;
push_back(first, last, x);
}
if(first)
pop_front(first);
print(first);
}*/
//My_Stack
/*#include<iostream>
using namespace std;
struct Stack
{
int val;
Stack* adr;
};
void Push(Stack* &first, int x)
{
Stack* crt;
crt = new Stack;
crt->val = x;
crt->adr = first;
first = crt;
}
void Pop(Stack* &first)
{
Stack* p;
p = first;
first = first->adr;
delete p;
}
bool isEmpty(Stack* first)
{
return !first;
}
int Top(Stack* first)
{
return first->val;
}
int main()
{
Stack* first = 0;
int n, x;
cin >> n;
for (int i = 0;i < n;i++)
{
cin >> x;
Push(first, x);
}
while (!isEmpty(first))
{
cout << Top(first) << " ";
Pop(first);
}
}*/
/*#include<iostream>
using namespace std;
struct Stack
{
char val;
Stack* adr;
};
void Push(Stack*& first, int x)
{
Stack* crt;
crt = new Stack;
crt->val = x;
crt->adr = first;
first = crt;
}
void Pop(Stack*& first)
{
Stack* p;
p = first;
first = first->adr;
delete p;
}
bool isEmpty(Stack* first)
{
return !first;
}
char Top(Stack* first)
{
return first->val;
}
int main()
{
Stack* crt, * first, * p;
int i, n, x;
char a;
first = 0;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> a;
if (!isEmpty(first))
{
if (a == ')' and first->val == '(')
Pop(first);
else
Push(first, a);
}
else
Push(first, a);
}
if (isEmpty(first) == 0)
cout << "NU";
else
cout << "DA";
}*/
//Tema pregatire
/*#include<iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int x = n, y = m;
while (m and n > 1)
{
n -= 2;
m--;
}
cout << n << " ";
if (x - 1 <= y)
cout << 0;
else
cout << x - 1 - y;
}*/
/*#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, m, k, x, y;
cin >> n >> m >> k;
vector<vector<int>> M(n + 1);
for (int i = 0;i < m;i++)
{
cin >> x >> y;
M[x].push_back(y);
}
int nr = 0;
for (int i = 1;i <= n;i++)
if (i % k != 0)
{
int sz = M[i].size();
for (int j = 0;j < sz;j++)
if (M[i][j] % k != 0)
nr++;
}
cout << nr;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<set>
using namespace std;
ifstream fin("subgraf.in");
ofstream fout("subgraf.out");
bool isprime(int k)
{
if (k == 1)
return 0;
if (k == 2)
return 1;
if (k % 2 == 0)
return 0;
for (int i = 3;i < k / 2;i++)
if (k % i == 0)
return 0;
return 1;
}
int main()
{
int n, x, y, nr = 0;
fin >> n;
vector<set<int> > M(n + 1);
while (fin >> x >> y)
if (x < y)
M[x].insert(y);
else
M[y].insert(x);
for (int i = 1;i <= n;i++)
if (!isprime(i))
for (auto t : M[i])
if (!isprime(t))
nr++;
fout << nr;
}*/
//Graph
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define ULL unsinged long long
ifstream fin("graf.in");
int n, m;
vector<pair<vector<int>, int> > G;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
for (int i = 0;i < m;i++)
{
fin >> x >> y;
G[x].first.push_back(y);
G[y].first.push_back(x);
G[x].second++;
G[y].second++;
}
}
void print()
{
for (int i = 1;i <= n;i++)
{
cout << i << " : ";
int sz = G[i].first.size();
for (int j = 0;j < sz;j++)
cout << G[i].first[j] << " ";
cout << endl;
}
}
int main()
{
read();
print();
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<map>
using namespace std;
vector<vector<int> > G;
vector<int> lant;
int n, m, vf;
map<int, int> M;
map<pair<int, int>, int > M1;
void ReadGraph()
{
int x, y, i;
ifstream fin("graf.in");
fin >> n >> m;
G.resize(n + 1);
for (i = 1; i <= m; i++)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
fin >> vf;
lant.resize(vf);
for (i = 0; i < vf; i++)
{
fin >> lant[i];
M[lant[i]]++;
if (i > 0)
M1[{lant[i], lant[i - 1]}]++;
}
}
bool Elementar()
{
for (auto x : M)
if (x.second > 1)
return 0;
return 1;
}
bool Lant()
{
for (auto i = 0; i < vf - 1; i++)
if (find(G[lant[i]].begin(), G[lant[i]].end(), lant[i + 1]) ==
G[lant[i]].end())
return 0;
return 1;
}
void WriteGraph()
{
int i, j;
for (i = 1; i <= n; i++)
{
cout << i << ": ";
for (j = 0; j < G[i].size(); j++)
cout << G[i][j] << " ";
cout << endl;
}
}
bool Ciclu()
{
if (vf < 3)
return 0;
if (!Lant())
return 0;
if (lant[0] != lant[vf - 1])
return 0;
for (auto t : M1)
if (t.second > 1)
return 0;
return 1;
}
int main()
{
ReadGraph();
if (Lant() == 1)
{
cout << "Lant ";
if (Elementar())
cout << "elementar" << endl;
else
cout << "neelementar" << endl;
}
else
cout << "Nu e lant" << endl;
if (Ciclu())
cout << "E ciclu";
else
cout << "Nu e ciclu";
}*/
/*#include<iostream>
#include<string>
#include<vector>
#include<map>
using namespace std;
int main()
{
int n, m;
cin >> n;
string name, game;
map<string, vector<string> > M;
for (int i = 0;i < n;i++)
{
cin >> name >> m;
for (int j = 0;j < m;j++)
{
cin >> game;
M[game].push_back(name);
}
}
cin >> game;
cout << M[game].size();
}*/
/*#include<iostream>
#include<fstream>
#include<string>
#include<map>
using namespace std;
int main()
{
ifstream fin("graf.in");
string word, cuvant;
map<string, short> M;
int m = 0;
while (cin >> word)
{
M[word]++;
if (m < M[word])
{
m = M[word];
cuvant = word;
}
}
cout << cuvant;
}*/
//Graph
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
int n, m, start;
vector<vector<int> > G;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
for (int i = 0;i < m;i++)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Breadth_first(int start)
{
queue<int> Q;
vector<int> viz(n + 1);
Q.push(start);
viz[start] = 1;
int crt, sz;
while (!Q.empty())
{
crt = Q.front();
Q.pop();
cout << crt << " ";
sz = G[crt].size();
for (int j = 0;j < sz;j++)
if (viz[G[crt][j]] == 0)
{
Q.push(G[crt][j]);
viz[G[crt][j]] = 1;
}
}
}
int main()
{
read();
Breadth_first(1);
}*/
//Exercitii
/*#include<fstream>
#include<cmath>
using namespace std;
ifstream fin("bomboane.in");
ofstream fout("bomboane.out");
int main()
{
int c, n, x, y;
fin >> c >> n >> x >> y;
if (c == 1)
fout << n / x;
else
if (c == 2)
{
int X = 2;
for (int i = 2;i <= n / 2;i++)
if (n % i == 0)
{
X = i;
break;
}
fout << n / X;
}
else
{
int B = 0, X = 0, r = n;
for (int i = n / y;i >= x;i--)
if (r > n % i and n / i >= y)
{
r = n % i;
B = n / i;
X = i;
if (r == 0)
break;
}
fout << r << " " << X << " " << B;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("microbist.in");
ofstream fout("microbist.out");
int main()
{
int c, n, x;
pair<int, int> goal;
fin >> c >> n;
if (c == 1)
{
for (int i = 0;i < n;i++)
{
fin >> x;
if (x == 1)
goal.first++;
else
goal.second++;
}
fout << goal.first << " " << goal.second;
}
else
if (c == 2)
{
int nr = 0;
for (int i = 0;i < n;i++)
{
fin >> x;
if (goal.first == goal.second)
nr++;
if (x == 1)
goal.first++;
else
goal.second++;
}
if (goal.first == goal.second)
nr++;
fout << nr;
}
else
{
int lead, come_back = 0, max_come_back = 0;
vector<pair<int, int> > v;
for (int i = 0;i < n;i++)
{
fin >> x;
if (v.empty())
v.push_back({ 1,x });
else
if (v[v.size() - 1].second == x)
v[v.size() - 1].first++;
else
v.push_back({ 1,x });
}
int sz = v.size();
lead = v[0].second;
if (v[0].second == 1)
goal.first += v[0].first;
else
goal.second += v[0].first;
for (int i = 1;i < sz;i++)
{
if (v[i].second == 1)
goal.first += v[i].first;
else
goal.second += v[i].first;
if (lead != v[i].second)
{
if (lead == 1)
{
if (goal.first < goal.second)
come_back = goal.first - goal.second + v[i].first + 1;
if (max_come_back < come_back)
max_come_back = come_back;
lead = 2;
}
else
{
if (goal.first > goal.second)
come_back = goal.second - goal.first + v[i].first + 1;
if (max_come_back < come_back)
max_come_back = come_back;
lead = 1;
}
}
}
fout << max_come_back;
}
}*/
/*#include<iostream>
#include<fstream>
#include<unordered_map>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
ifstream fin("perechi.in");
ofstream fout("perechi.out");
int oglindit(int x)
{
int o = 0;
while (x)
{
o = o * 10 + x % 10;
x /= 10;
}
return o;
}
string palindrom(string x)
{
int sz = x.length();
string rev = "";
for (int i = sz - 1;i >= 0;i--)
rev += x[i];
return rev;
}
void print(unordered_map<int, int> M)
{
for (auto t : M)
cout << t.first << " " << t.second << " ";
cout << endl;
}
bool crt(string a, string b)
{
int sza = a.length(), szb = b.length();
if (sza != szb)
return sza > szb;
return a > b;
}
int main()
{
int c;
fin >> c;
if (c == 1)
{
int n, nr = 0, p, x;
fin >> n;
unordered_map<int, int> M;
for (int i = 0;i < n;i++)
{
fin >> x;
if (x % 10 != 0)
{
int og = oglindit(x);
if (M.find(og) != M.end())
{
if (M[og] == 0)
M[og] = 1;
else
M[og]++;
}
}
if (M[x] == 0)
M[x] = 0;
}
for (auto t : M)
if(t.second)
{
//t.second++;
nr += (t.second * (t.second + 1)) / 2;
}
fout << nr;
}
else
{
int n;
fin >> n;
vector<string> v(n);
for (int i = 0;i < n;i++)
fin >> v[i];
sort(v.begin(), v.end(), crt);
for (int i = 1;i <= 9;i++)
v.pop_back();
bool ok = 1;
int sz = v.size();
for (int i = 0;i < sz - 1 and ok;i++)
for (int j = i + 1;j < sz and ok;j++)
if (v[i] + v[j] == palindrom(v[i] + v[j]) and v[j] != "9")
{
fout << v[i] << v[j];
ok = 0;
}
else
if (v[j] + v[i] == palindrom(v[j] + v[i]) and v[j] != "9")
{
fout << v[j] << v[i];
ok = 0;
}
}
}*/
/*#include<iostream>
#include<fstream>
std::ifstream fin("avid.in");
std::ofstream fout("avid.out");
int Cmmdc(int n, int m)
{
while (m)
{
int r = n % m;
n = m;
m = r;
}
return n;
}
int div(int x)
{
int nr = 1, e = 1;
while (x % 2 == 0)
{
e++;
x /= 2;
}
nr *= e;
for (int i = 3;i * i <= x;i += 2)
{
e = 1;
while (x % i == 0)
{
e++;
x /= i;
}
nr *= e;
}
if (x > 1)
nr *= 2;
return nr;
}
int main()
{
int n;
short c, p;
int nr = 0, cmmdc, DIVp;
fin >> c >> n >> p;
int x, y, z;
fin >> x >> y;
if (c == 1)
{
for (int i = 0;i < n - 2;i++)
{
fin >> z;
cmmdc = Cmmdc(x, Cmmdc(y, z));
DIVp = div(cmmdc);
if (DIVp <= p)
nr++;
x = y;
y = z;
}
fout << nr;
}
else
{
int maxy = 0, crt = 2;
for (int i = 0;i < n - 2;i++)
{
fin >> z;
cmmdc = Cmmdc(x, Cmmdc(y, z));
DIVp = div(cmmdc);
if (DIVp > p)
{
if (maxy < crt)
maxy = crt;
crt = 2;
}
else
crt++;
x = y;
y = z;
}
if (crt > maxy)
maxy = crt;
fout << maxy;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<int> visited;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
visited.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void DST(int vf,int nr)
{
queue<int> Q;
Q.push(vf);
int crt;
visited[vf] = nr;
while (!Q.empty())
{
crt = Q.front();
Q.pop();
int sz = G[crt].size();
for (int j = 0;j < sz;j++)
if (visited[G[crt][j]] == 0)
{
visited[G[crt][j]] = nr;
Q.push(G[crt][j]);
}
}
}
int main()
{
read();
int nr = 0;
for (int i = 1;i <= n;i++)
if (visited[i] == 0)
{
nr++;
DST(i, nr);
}
if (nr != 1)
cout << "Neconex" << endl;
for (int i = 1;i <= nr;i++)
{
cout << i << " : ";
for (int j = 1;j <= n;j++)
if (visited[j] == i)
cout << j << " ";
cout << endl;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> visited;
vector<int> dst;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
visited.resize(n + 1);
dst.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void DST(int vf)
{
queue<int> Q;
Q.push(vf);
int crt;
visited[vf] = 1;
while (!Q.empty())
{
crt = Q.front();
Q.pop();
int sz = G[crt].size();
for (int j = 0;j < sz;j++)
if (visited[G[crt][j]] == 0)
{
visited[G[crt][j]] = 1;
dst[G[crt][j]] = dst[vf] + 1;
Q.push(G[crt][j]);
}
}
}
int main()
{
read();
DST(1);
for (int i = 1;i <= n;i++)
cout << dst[i] << " ";
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("parking.in");
ofstream fout("parking.out");
vector<vector<int> > M;
int n, m, k, q;
void read()
{
M.resize(n + 2);
for (int i = 0;i <= n + 1;i++)
M[i].resize(m + 2);
for (int i = 0;i <= n + 1;i++)
M[i][0] = M[i][m + 1] = -1;
for (int j = 0;j <= m;j++)
M[0][j] = M[n + 1][j] = -1;
int x, y, p;
for (int i = 0;i < k;i++)
{
fin >> x >> y;
M[x][y] = -2;
}
for (int i = 0;i < q;i++)
{
fin >> x >> y >> p;
M[x][y] = p + 1;
}
}
bool fill1(int x, int y)
{
bool ok1 = 0, ok2 = 0;
if (M[x][0] == -2)
{
ok1 = 1;
for (int j = y - 1;j > 0 and ok1;j--)
if (M[x][j])
ok1 = 0;
}
if (M[x][m + 1] == -2)
{
ok2 = 1;
for (int j = y + 1;j <= m and ok2;j++)
if (M[x][j])
ok2 = 0;
}
return (ok1 or ok2);
}
bool fill2(int x, int y)
{
bool ok1 = 0, ok2 = 0;
if (M[0][y] == -2)
{
ok1 = 1;
for (int i = x - 1;i > 0 and ok1;i--)
if (M[i][y])
ok1 = 0;
}
if (M[n + 1][y] == -2)
{
ok2 = 1;
for (int i = x + 1;i <= n and ok2;i++)
if (M[i][y])
ok2 = 0;
}
return (ok1 or ok2);
}
int main()
{
short c;
fin >> c >> n >> m >> k >> q;
read();
if (c == 1)
{
int nr = 0;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (M[i][j] == 1)
nr += fill1(i, j);
else
if (M[i][j] == 2)
nr += fill2(i, j);
fout << nr;
}
else
{
pair<int, int> sol = { 0,0 }, crt;
queue<pair<int, int> > Q;
bool Do;
int dif = -1;
while (dif != sol.first)
{
dif = sol.first;
sol.second++;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (M[i][j] == 1)
{
Do = fill1(i, j);
if (Do)
{
sol.first++;
Q.push({ i,j });
}
}
else
if (M[i][j] == 2)
{
Do = fill2(i, j);
if (Do)
{
sol.first++;
Q.push({ i,j });
}
}
while (!Q.empty())
{
crt = Q.front();
Q.pop();
M[crt.first][crt.second] = 0;
}
}
fout << sol.first << " " << sol.second - 1;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("ron.in");
ofstream fout("ron.out");
vector<int> v(100002);
void getv()
{
for (int i = 2;i * i <= 100000;i++)
if (!v[i])
{
v[i * i] = 2;
int j = i + 1;
while (j * i <= 100000)
{
v[j * i] = 1;
j++;
}
}
}
bool isprime(int x)
{
if (!x or x == 1)
return 0;
if (x % 2 == 0)
return 0;
for (int i = 3;i * i <= x;i += 2)
if (x % i == 0)
return 0;
return 1;
}
bool add(int x)
{
int i;
for (i = 2;i * i <= x;i++);
if (isprime(i - 1))
return ((i - 1) * (i - 1) == x);
return 0;
}
int power(int x, int y)
{
int val = 0;
for (int i = x;y;i++, y--)
if (v[i] == 2)
val++;
return val;
}
int main()
{
short c;
int n, x, y;
fin >> c >> n;
if (c == 1)
{
getv();
pair<pair<int, int>, int> sol = { {0,0},0 };
while (fin >> x >> y)
if (x + y >= sol.first.first and sol.first.first >= x)
{
sol.first.first = x;
if (sol.first.second < y)
sol.first.second = y;
sol.second += power(sol.first.first, sol.first.second);
}
else
if (sol.first.first <= x + y and sol.first.first <= x)
{
if (sol.first.second < y)
sol.first.second = y;
sol.second += power(sol.first.first, sol.first.second);
}
else
{
int crt = power(x, y);
if (crt > sol.second)
{
sol.second = crt;
sol.first.first = x;
sol.first.second = y;
}
}
fout << sol.second;
}
else
{
vector<pair<int, int> > v;
while (fin >> x >> y)
{
int sz = v.size();
bool Do = 1;
for (int i = sz - 1;i >= 0 and Do;i--)
if (x + y >= v[i].first and x <= v[i].first)
{
Do = 0;
v[i].first = x;
if (v[i].second < y)
v[i].second = y;
}
else
if (v[i].first + v[i].second >= x and v[i].first <= x)
{
Do = 0;
if (v[i].second < y)
v[i].second = y;
}
if (Do == 1)
v.push_back({ x,y });
}
fout << v.size();
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> vstd;
vector<int> d;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
d.resize(n + 1);
vstd.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void breadth_first(int start)
{
queue<int> Q;
Q.push(start);
int crt;
vstd[start] = 1;
while (!Q.empty())
{
crt = Q.front();
Q.pop();
for (auto t : G[crt])
if (!vstd[t])
{
vstd[t] = 1;
Q.push(t);
d[t] = crt;
}
}
}
void Lant(int x)
{
while (x)
{
cout << x << " ";
x = d[x];
}
}
void Lant1(int x)
{
stack<int> S;
while (x)
{
S.push(x);
x = d[x];
}
while (!S.empty())
{
cout << S.top() << " ";
S.pop();
}
}
void Lant2(int x)
{
if (x)
{
Lant2(d[x]);
cout << x << " ";
}
}
int main()
{
read();
breadth_first(1);
Lant2(8);
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> vstd;
vector<int> d;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
d.resize(n + 1);
vstd.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void breadth_first(int start)
{
queue<int> Q;
Q.push(start);
int crt;
vstd[start] = 1;
while (!Q.empty())
{
crt = Q.front();
Q.pop();
for (auto t : G[crt])
if (!vstd[t])
{
vstd[t] = 1;
Q.push(t);
d[t] = crt;
}
}
}
void Lant(int x)
{
while (x != 1)
{
cout << x << " ";
x = d[x];
}
}
void Lant2(int x)
{
if (x)
{
Lant2(d[x]);
cout << x << " ";
}
}
int main()
{
read();
breadth_first(1);
Lant(3);
Lant2(8);
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> vstd;
vector<int> d;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
d.resize(n + 1);
vstd.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void depth_first(int start)
{
cout << start << " ";
vstd[start] = true;
for (int t : G[start])
if (!vstd[t])
depth_first(t);
}
int main()
{
read();
depth_first(1);
}*/
/*#include<iostream>
#include<fstream>
#include<string>
#include<unordered_map>
#include<set>
#include<algorithm>
using namespace std;
ifstream fin("mun.in");
ofstream fout("mun.out");
int main()
{
int c, n;
string code;
fin >> c >> n;
if (c == 1)
{
unordered_map<string, int> M;
while (fin >> code)
{
sort(code.begin(), code.end());
M[code] = 1;
}
fout << M.size();
}
else
if (c == 2)
{
unordered_map<string, int> M;
while (fin >> code)
{
sort(code.begin(), code.end());
M[code]++;
}
set<int> S;
for (pair<string, int> t : M)
S.insert(t.second);
set<int>::iterator s = S.begin();
int val = *S.rbegin();
while (val >= *s)
{
val -= *s;
s++;
}
fout << val << " " << n - val;
}
}*/
/*#include<iostream>
#include<fstream>
#include<map>
#include<deque>
using namespace std;
ifstream fin("robotron.in");
ofstream fout("robotron.out");
int main()
{
short c;
fin >> c;
int n, l, k;
fin >> n >> l >> k;
if (c == 1)
{
int x, y;
map<int, int> M;
while (fin >> x >> y)
{
int code = x % 10;
code += 10 * (x / 10 % 10);
M[code]++;
}
fout << M.size() << " ";
pair<int, int> t = *M.begin();
for (pair<int, int> m : M)
if (t.second < m.second)
t = m;
fout << t.first;
}
else
{
map<int, deque<pair<int, int> > > M;
int x, y;
while (fin >> x >> y)
{
int code = x % 10;
code += 10 * (x / 10 % 10);
M[code].push_back({ x / 100,y });
}
pair<int, int> winner;
for (int i = 0;i < k;i++)
{
pair<int, pair<int, int> > maxy = { 0,{0,0} };
for (pair<int, deque<pair<int, int> > > t : M)
{
if (maxy.second.second < t.second.front().second)
maxy = { t.first,t.second.front() };
}
winner = { maxy.first,maxy.second.first };
for (pair<int, deque<pair<int, int> > > t : M)
{
M[t.first].push_back(t.second.front());
M[t.first].pop_front();
}
}
fout << winner.first << " " << winner.second;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("macarie.in");
ofstream fout("macarie.out");
int main()
{
int n, q, j, x;
fin >> n >> q;
vector<int> A(n), D(n, 1);
for (int i = 0;i < n;i++)
fin >> A[i];
for (int i = 0;i < n;i++)
{
D.push_back(A[i]);
for (j = 2;j * j < A[i];j++)
if (A[i] % j == 0)
{
D.push_back(j);
D.push_back(A[i] / j);
}
if (j * j == A[i])
D.push_back(j);
}
sort(D.begin(), D.end());
for (int i = 0;i < q;i++)
{
fin >> x;
fout << D[x - 1] << " ";
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("santinele.in");
ofstream fout("santinele.out");
short c;
fin >> c;
int n, k;
fin >> n >> k;
if (c == 1)
{
vector<int> v(n);
for (int i = 0;i < n;i++)
fin >> v[i];
int maxd = 1;
for (int i = 0;i < k;i++)
{
int nr = 1;
for (int j = i + 1;j <= i + k;j++)
if (v[i] >= v[j])
nr++;
else
break;
for (int j = i - 1;j >= 0;j--)
if (v[i] >= v[j])
nr++;
else
break;
if (maxd < nr)
maxd = nr;
}
fout << maxd;
}
else
{
vector<int> v(n);
for (int i = n - 1;i >= 0;i--)
fin >> v[i];
int maxd = 1, count = 0;
for (int j = 0;j < n;j += maxd)
{
for (int i = j;i < k;i++)
{
int nr = 1;
for (int j = i + 1;j <= i + k;j++)
if (v[i] >= v[j])
nr++;
else
break;
for (int j = i - 1;j >= 0;j--)
if (v[i] >= v[j])
nr++;
else
break;
if (maxd < nr)
maxd = nr;
}
count++;
}
fout << count;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int Max = 0, n, m;
vector<vector<int> > M;
void print(int i1, int j1, int i2, int j2)
{
for (int i = i1;i <= i2;i++)
{
for (int j = j1;j <= j2;j++)
cout << M[i][j] << " ";
cout << endl;
}
cout << endl;
}
int score_matrix(int i1, int j1, int i2, int j2)
{
int score = 0;
for (int i = i1;i <= i2;i++)
for (int j = j1;j <= j2;j++)
if (i % 2 == j % 2)
score += M[i][j];
else
score -= M[i][j];
return score;
}
void divide_matrix(int i1, int j1, int i2, int j2)
{
int score = score_matrix(i1, j1, i2, j2);
if (Max < score)
Max = score;
if (i1 <= i2 and j1 <= j2)
{
divide_matrix(i1 + 1, j1, i2, j2);
divide_matrix(i1, j1, i2 - 1, j2);
divide_matrix(i1, j1 + 1, i2, j2);
divide_matrix(i1, j1, i2, j2 - 1);
}
}
int main()
{
ifstream fin("trafalet.in");
ofstream fout("trafalet.out");
fin >> n >> m;
M.resize(n);
for (int i = 0;i < n;i++)
M[i].resize(m);
for (int i = 0;i < n;i++)
for (int j = 0;j < m;j++)
fin >> M[i][j];
divide_matrix(0, 0, n - 1, m - 1);
fout << Max;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
int n, m;
void read()
{
int x, y;
fin >> n >> m;
G.resize(n + 1);
viz.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void print()
{
for (int i = 1;i <= n;i++)
{
cout << i << " : ";
for (int j : G[i])
cout << j << " ";
cout << '\n';
}
}
int nr_izolated()
{
int nr = 0;
for (int i = 1;i <= n;i++)
if (!G[i].size())
nr++;
return nr;
}
void dfs(int x)
{
cout << x << " ";
viz[x] = true;
for (auto t : G[x])
if (!viz[t])
dfs(t);
}
int main()
{
read();
dfs(1);
}*/
//Tema pregatire
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
viz.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void print()
{
for (int i = 1;i <= n;i++)
{
cout << i << " : ";
for (int j : G[i])
cout << j << " ";
cout << '\n';
}
}
void dfs1(int k, int& nr)
{
viz[k] = true;
for (int t : G[k])
if (!viz[t])
{
viz[t] = true;
nr++;
dfs1(t, nr);
}
}
void dfs2(int k)
{
viz[k] = true;
for (int t : G[k])
if (!viz[t])
{
viz[t] = true;
dfs2(t);
}
}
void dfs3(int k)
{
viz[k] = true;
cout << k << " ";
for (int t : G[k])
if (!viz[t])
{
viz[t] = true;
dfs3(t);
}
}
int main()
{
short c;
fin >> c;
read();
if (c == 1)
{
int nr = 1;
dfs1(1, nr);
if (nr == n)
cout << "conex";
else
cout << "neconex";
}
else
if (c == 2)
{
int nr = 0;
for (int i = 1;i <= n;i++)
if (!viz[i])
{
nr++;
dfs2(i);
}
cout << nr;
}
else
for (int i = 1;i <= n;i++)
if (!viz[i])
{
dfs3(i);
cout << '\n';
}
}*/
//Exercitii
/*include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("tablou.in");
ofstream fout("tablou.out");
short p;
fin >> p;
if (p == 1)
{
int n, k;
fin >> n >> k;
vector<vector<bool> > M(n);
for (int i = 0;i < n;i++)
M[i].resize(n, 1);
for (int i = 0;i < k;i++)
{
char c;
int x;
fin >> c >> x;
if (c == 'L')
for (int j = 0;j < n;j++)
M[x - 1][j] = !M[x - 1][j];
else
for (int j = 0;j < n;j++)
M[j][x - 1] = !M[j][x - 1];
}
int nr = 0;
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
if (M[i][j] == 1)
nr++;
fout << nr;
}
else
{
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<map>
using namespace std;
#define MOD 1000003
ifstream fin("triunghiuri.in");
ofstream fout("triunghiuri.out");
vector<pair<int, int> > v;
vector<bool> viz;
vector<int> c(4);
int n;
void C(int k, int& nr)
{
if (k == 4)
{
if (v[c[1]].first != v[c[2]].first and v[c[1]].first != v[c[3]].first and v[c[2]].first != v[c[3]].first)
{
if (v[c[1]].second == v[c[2]].second and v[c[1]].second != v[c[3]].second)
nr = (nr + 1) % MOD;
else
if (v[c[1]].second == v[c[3]].second and v[c[1]].second != v[c[2]].second)
nr = (nr + 1) % MOD;
else
if (v[c[2]].second == v[c[3]].second and v[c[2]].second != v[c[1]].second)
nr = (nr + 1) % MOD;
}
}
else
for (int i = c[k - 1] + 1;i <= n;i++)
if (!viz[i])
{
c[k] = i;
viz[i] = true;
C(k + 1, nr);
viz[i] = false;
}
}
int main()
{
short p;
fin >> p >> n;
if (p == 1)
{
int nr = 0;
map<int, int> M;
for (int i = 0;i < n;i++)
{
int x, y;
fin >> x >> y;
M[x]++;
}
for (pair<int, int> t : M)
if (nr < t.second)
nr = t.second;
fout << nr;
}
else
{
int nr = 0;
v.resize(n + 1);
viz.resize(n + 1);
for (int i = 1;i <= n;i++)
fin >> v[i].first >> v[i].second;
C(1, nr);
fout << nr;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
viz.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int k)
{
stack<int> S;
cout << k << " ";
S.push(k);
viz[k] = true;
while (!S.empty())
{
int vf = S.top();
bool ok = false;
for (int t : G[vf])
if (!viz[t])
{
S.push(t);
cout << t << " ";
viz[t] = true;
ok = true;
break;
}
if (!ok)
S.pop();
}
}
int main()
{
read();
dfs(1);
}*/
/*#include<iostream>
#include<fstream>
using namespace std;
int main()
{
ifstream fin("bac.txt");
int s, x, smax;
fin >> s;
smax = s;
while (fin >> x)
{
if (x > s + x)
s = x;
else
s += x;
if (smax < s)
smax = s;
}
cout << smax;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
int i, s, smax, x;
vector<int> dp;
ifstream fin("bac.txt");
fin >> x;
dp.push_back(x);
smax = x;
while (fin >> x)
{
if (*dp.rbegin() + x < x)
dp.push_back(x);
else
dp.push_back(*dp.rbegin() + x);
if (*dp.rbegin() > smax)
smax = *dp.rbegin();
}
cout << smax;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
vector<int> Length, T;
int n, m, start;
void read()
{
fin >> n >> m;
G.resize(n + 1);
viz.resize(n + 1);
Length.resize(n + 1);
T.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start] = 1;
int vf;
Length[start] = 0;
T[start] = 0;
while (!Q.empty())
{
vf = Q.front();
for (int vec : G[vf])
if (viz[vec] == 0)
{
cout << vec << " ";
Q.push(vec);
viz[vec] = 1;
Length[vec] = Length[vf] + 1;
T[vec] = vf;
}
Q.pop();
}
}
int main()
{
read();
bfs(4);
cout << endl;
for (int i = 1;i <= n;i++)
cout << Length[i] << " ";
cout << endl;
for (int i = 1;i <= n;i++)
cout << T[i] << " ";
}*/
//Stack-sort
/*#include<iostream>
#include<stack>
using namespace std;
void print(stack<int>& S)
{
if (!S.empty())
{
int x = S.top();
S.pop();
print(S);
cout << x << " ";
}
}
void print_rev(stack<int>& S)
{
if (!S.empty())
{
cout << S.top() << " ";
S.pop();
print_rev(S);
}
}
void Insert(stack<int>& move2, stack<int>& move1)
{
if (!move2.empty())
{
move1.push(move2.top());
move2.pop();
Insert(move2, move1);
}
}
int main()
{
stack<int> S, move1, move2;
int x;
for (cin >> x;x;cin >> x)
S.push(x);
if (!S.empty())
{
move1.push(S.top());
S.pop();
}
while (!S.empty())
{
if (S.top() < move1.top())
while (!move1.empty() and move1.top() > S.top())
{
move2.push(move1.top());
move1.pop();
}
move1.push(S.top());
S.pop();
Insert(move2, move1);
}
print(move1);
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
bool bfs(int start)
{
int nr = 1, nod;
queue<int> Q;
Q.push(start);
viz[start] = true;
while (!Q.empty())
{
nod = Q.front();
Q.pop();
for (int t : G[nod])
if (!viz[t])
{
viz[t] = true;
nr++;
Q.push(t);
}
}
return (nr == n);
}
int main()
{
read();
cout << bfs(1);
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start)
{
viz[start] = true;
queue<int> Q;
Q.push(start);
int nod;
while (!Q.empty())
{
nod = Q.front();
Q.pop();
for (int t : G[nod])
if (!viz[t])
{
Q.push(t);
viz[t] = true;
}
}
}
int main()
{
read();
int nr = 0;
for (int i = 1;i <= n;i++)
if (!viz[i])
{
nr++;
bfs(i);
}
cout << nr;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start] = true;
int nod;
cout << start << " ";
while (!Q.empty())
{
nod = Q.front();
Q.pop();
for (int t : G[nod])
if (!viz[t])
{
viz[t] = true;
Q.push(t);
cout << t << " ";
}
}
}
int main()
{
read();
for (int i = 1;i <= n;i++)
if (!viz[i])
{
bfs(i);
cout << '\n';
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<bool> viz;
vector<int> Length;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
Length.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
int bfs(int start, int end)
{
queue<int> Q;
Q.push(start);
viz[start] = true;
int nod;
Length[start] = 0;
while (!Q.empty())
{
nod = Q.front();
Q.pop();
for (int t : G[nod])
if (!viz[t])
{
viz[t] = true;
Length[t] = Length[nod] + 1;
if (t == end)
return Length[t];
Q.push(t);
}
}
retrun -1;
}
int main()
{
int x, y;
fin >> x >> y;
read();
cout << bfs(x, y);
}*/
/*#include<iostream>
#include<fstream>
using namespace std;
int main()
{
int x, s, smin;
ifstream fin("bac.txt");
fin >> s;
smin = s;
while (fin >> x)
{
if (x > s + x)
s += x;
else
s = x;
if (smin > s)
smin = s;
}
cout << smin;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("bac.txt");
int main()
{
int n, s = 0, maxneg = 0;
bool ok = false;
vector<int> v;
while (fin >> n)
v.push_back(n);
for (int i : v)
{
if (i > 0)
s += i;
else
if (i == 0)
ok = true;
else
{
if (maxneg == 0)
maxneg = i;
else
if (maxneg < i)
maxneg = i;
}
}
if (!s and !ok)
s = maxneg;
cout << s;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
int main()
{
std::vector<int> v, dp;
std::ifstream fin("bac.txt");
int n;
while (fin >> n)
v.push_back(n);
dp.resize(v.size());
dp[0] = v[0];
for (int i = 1;i < n;i++)
if (dp[i - 1] + v[i] < dp[i - 1])
dp[i] = dp[i - 1];
else
dp[i] = dp[i - 1] + v[i];
std::cout << dp[v.size() - 1];
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<int> viz;
int n, m;
bool ok = true;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start] = 1;
int nod;
while (!Q.empty())
{
nod = Q.front();
Q.pop();
for (int t : G[nod])
if (!viz[t])
{
Q.push(t);
if (viz[nod] == 1)
viz[t] = 2;
else
viz[t] = 1;
}
else
if (viz[nod] == viz[t])
ok = false;
}
}
int main()
{
read();
bfs(1);
if (!ok)
cout << "nu este";
else
{
for (int i = 1;i <= n;i++)
if (viz[i] == 1)
cout << i << " ";
cout << endl;
for (int i = 1;i <= n;i++)
if (viz[i] == 2)
cout << i << " ";
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<int> viz;
int n, m;
bool ok = true;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start] = 1;
int nod;
while (!Q.empty())
{
nod = Q.front();
Q.pop();
for (int t : G[nod])
if (!viz[t])
{
Q.push(t);
viz[t] = -viz[nod];
}
else
if (viz[nod] == viz[t])
ok = false;
}
}
int main()
{
read();
bfs(1);
if (!ok)
cout << "nu este";
else
{
for (int i = 1;i <= n;i++)
if (viz[i] == 1)
cout << i << " ";
cout << '\n';
for (int i = 1;i <= n;i++)
if (viz[i] == -1)
cout << i << " ";
}
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<int> viz;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
viz.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
bool bfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start] = 1;
while (!Q.empty())
{
for (int t : G[Q.front()])
if (!viz[t])
{
viz[t] = -viz[Q.front()];
Q.push(t);
}
else
if (viz[t] == viz[Q.front()])
return false;
Q.pop();
}
return true;
}
int main()
{
read();
if (bfs(1))
{
for (int i = 1;i <= n;i++)
if (viz[i] == 1)
cout << i << " ";
cout << '\n';
for (int i = 1;i <= n;i++)
if (viz[i] == -1)
cout << i << " ";
}
else
cout << "nu este";
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<int> viz;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
viz.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
bool dfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start] = 1;
while (!Q.empty())
{
for (int t : G[Q.front()])
if (!viz[t])
{
Q.push(t);
viz[t] = Q.front() + 1;
}
else
if (viz[t] == viz[Q.front()] + 1)
return true;
Q.pop();
}
return false;
}
int main()
{
read();
cout << dfs(1);
}*/
/*#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n, smin = 0, nrmin = 100000;
bool ok = false;
cin >> n;
vector<int> v(n);
for (int i = 0;i < n;i++)
cin >> v[i];
for (int i = 0;i < n;i++)
if (v[i] <= 0)
{
ok = true;
smin += v[i];
}
else
if (nrmin > v[i])
nrmin = v[i];
if (ok)
cout << smin;
else
cout << nrmin;
}*/
//c)n - 4
//e)(n - 2) * (n - 3) / 2
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("bac.txt");
vector<int> v = { 5, 10, 7, 4, 5, 8, 9, 8, 10, 2 }, lg(10, 1);
int n = 10, maxy = 1;
for (int i = n - 1;i >= 0;i--)
{
for (int j = i + 1;j < n;j++)
if (v[i] < v[j] and lg[i] < lg[j] + 1)
lg[i] = lg[j] + 1;
if (lg[i] > maxy)
maxy = lg[i];
}
cout << maxy;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("bac.txt");
vector<int> v = { 5, 10, 7, 4, 5, 8, 9, 8, 10, 2 }, lg(10, 1), pred(10);
int n = 10, maxy = 1, pmax;
pred[n - 1] = -1;
pmax = n - 1;
for (int i = n - 1;i >= 0;i--)
{
pred[i] = -1;
for (int j = i + 1;j < n;j++)
if (v[i] < v[j] and lg[i] < lg[j] + 1)
{
lg[i] = lg[j] + 1;
pred[i] = j;
}
if (lg[i] > maxy)
{
maxy = lg[i];
pmax = i;
}
}
cout << maxy << endl;
while (pmax != -1)
{
cout << v[pmax] << " ";
pmax = pred[pmax];
}
}*/
//Triunghiul lui Pascal
/*#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int> > Pascal(n + 1, vector<int> (n + 1));
Pascal[0][0] = 1;
for (int i = 1;i <= n;i++)
{
Pascal[i][0] = 1;
for (int j = 1;j < i;j++)
Pascal[i][j] = Pascal[i - 1][j] + Pascal[i - 1][j - 1];
Pascal[i][i] = 1;
}
for (int i = 0;i <= n;i++)
{
for (int j = 0;j <= i;j++)
cout << Pascal[i][j] << " ";
cout << '\n';
}
}*/
/*#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n = 5, m = 3;
vector<int> N = { 0,1,7,3,9,8 }, M = { 0,7,5,8 };
vector<vector<int> > Dp(6, vector<int>(4));
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (N[i] == M[j])
Dp[i][j] = Dp[i - 1][j - 1] + 1;
else
Dp[i][j] = max(Dp[i - 1][j], Dp[i][j - 1]);
cout << Dp[n][m];
}*/
//Graf
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
vector<vector<int> > G;
vector<pair<int, int> > viz;
int n, m, x, y;
void divX(int n, int x)
{
for (int i = x * n; i >= x; i -= x)
if (i % x == 0)
cout << i << " ";
}
void read()
{
fin >> n >> m >> x >> y;
G.resize(n + 1);
viz.resize(n + 1);
int k, l;
while (fin >> k >> l)
{
G[k].push_back(l);
G[l].push_back(k);
}
}
void bfs(int start)
{
queue<int> Q;
Q.push(start);
viz[start].first = 1;
while (!Q.empty())
{
for (int t : G[Q.front()])
if (!viz[t].first)
{
viz[t].first = viz[Q.front()].first + 1;
viz[t].second = viz[Q.front()].first;
Q.push(t);
}
Q.pop();
}
}
void print(int end)
{
if (x != end)
{
print(viz[end].second);
fout << end << " ";
}
else
fout << x << " ";
}
int main()
{
read();
bfs(x);
fout << viz[y].first << '\n';
print(y);
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("sclm.in");
ofstream fout("sclm.out");
int n, maxy = 1;
fin >> n;
int pmax = n - 1;
vector<int> v(n), dp(n, 1), pred(n, -1);
for (int i = 0;i < n;i++)
fin >> v[i];
for (int i = n - 1;i >= 0;i--)
{
for (int j = i + 1;j < n;j++)
if (v[i] < v[j] and dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
pred[i] = j;
}
if (maxy <= dp[i])
{
maxy = dp[i];
pmax = i;
}
}
fout << maxy << '\n';
while (pmax != -1)
{
fout << pmax + 1 << " ";
pmax = pred[pmax];
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("plopi1.in");
ofstream fout("plopi1.out");
int n;
fin >> n;
int miny = 0;
vector<int> v(n), dp(n, 1);
for (int i = 0;i < n;i++)
fin >> v[i];
for (int i = n - 1;i >= 0;i--)
{
for (int j = i + 1;j < n;j++)
if (v[i] > v[j] and dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
if (miny < dp[i])
miny = dp[i];
}
fout << n - miny;
}*/
/*#include<iostream>
#include<fstream>
#include<string>
#include<vector>
using namespace std;
int main()
{
ifstream fin("lungimesubsircomunmaximal.in");
ofstream fout("lungimesubsircomunmaximal.out");
string word1, word2;
fin >> word1 >> word2;
int sz1 = word1.length(), sz2 = word2.length();
vector<vector<int> > M(sz1 + 1, vector<int>(sz2 + 1));
for (int i = 1; i <= sz1; i++)
for (int j = 1; j <= sz2; j++)
if (word1[i - 1] == word2[j - 1])
M[i][j] = M[i - 1][j - 1] + 1;
else
if (M[i][j - 1] > M[i - 1][j])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i - 1][j];
fout << M[sz1][sz2];
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("radiera.in");
ofstream fout("radiera.out");
int n, maxy = 0;
fin >> n;
vector<int> v(n), dp(n, 1);
for (int i = 0;i < n;i++)
fin >> v[i];
for (int i = n - 1;i >= 0;i--)
{
for (int j = i + 1;j < n;j++)
if (v[i] <= v[j] and dp[i] < dp[j] + 1)
dp[i] = dp[j] + 1;
if (maxy < dp[i])
maxy = dp[i];
}
fout << n - maxy;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("bac.txt");
int n;
fin >> n;
vector<vector<int> > M(n), dp(n);
for (int i = 0;i < n;i++)
M[i].resize(i + 1);
for (int i = 0;i < n;i++)
dp[i].resize(i + 1);
for (int i = 0;i < n;i++)
for (int j = 0;j <= i;j++)
fin >> M[i][j];
dp[n - 1] = M[n - 1];
for (int i = n - 2;i >= 0;i--)
for (int j = 0;j <= i;j++)
if (dp[i + 1][j] > dp[i + 1][j + 1])
dp[i][j] = dp[i + 1][j] + M[i][j];
else
dp[i][j] = dp[i + 1][j + 1] + M[i][j];
cout << dp[0][0];
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("bac.txt");
int n, m;
fin >> n >> m;
vector<vector<int> > dp(n + 1, vector<int>(m + 1));
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
fin >> dp[i][j];
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (dp[i - 1][j] > dp[i][j - 1])
dp[i][j] += dp[i - 1][j];
else
dp[i][j] += dp[i][j - 1];
cout << dp[n][m];
}*/
/*#include<iostream>
#include<fstream>
#include<string>
#include<vector>
using namespace std;
#define PASTREZ 0
#define MODIFIC 1
#define STERG 2
#define INSEREZ 3
struct Element
{
int cost;
int operatie;
};
string A, B;
int n, m;
vector<vector<Element> > T;
void COST()
{
int i, j, tmin, toperatie;
for (j = 0;j <= m;j++)
T[0][j].cost = j;
for (i = 0;i <= n;i++)
T[i][0].cost = i;
for (i = 1;i <= n;i++)
for (j = 1;j <= m;j++)
if (A[i - 1] == B[j - 1])
{
T[i][j].cost = T[i - 1][j - 1].cost;
T[i][j].operatie = PASTREZ;
}
else
{
tmin = T[i - 1][j].cost + 1;
toperatie = STERG;
if (tmin > T[i - 1][j - 1].cost + 1)
{
tmin = T[i - 1][j - 1].cost + 1;
toperatie = MODIFIC;
}
if (tmin > T[i][j - 1].cost + 1)
{
tmin = T[i][j - 1].cost + 1;
toperatie = INSEREZ;
}
T[i][j] = { tmin,toperatie };
}
}
void operatii()
{
int i = n, j = m;
while (i > 0 and j > 0)
{
if (T[i][j].operatie == PASTREZ)
{
cout << "P: " << A << endl;
i--;
j--;
}
else
if (T[i][j].operatie == MODIFIC)
{
A[i - 1] = B[j - 1];
cout << "M(" << i - 1 << "," << B[j - 1] << "): " << A << endl;
i--;
j--;
}
else
if (T[i][j].operatie == STERG)
{
A.erase(i - 1, 1);
cout << "S(" << i - 1 << "): " << A << endl;
i--;
}
else
{
A.insert(i, 1, B[j - 1]);
cout << "I(" << i << "," << B[j - 1] << "): " << A << endl;
j--;
}
}
while (i > 0)
{
A.erase(i - 1, 1);
cout << "S(" << i - 1 << "): " << A << endl;
i--;
}
while (j > 0)
{
A.insert(i, 1, B[j - 1]);
cout << "I(" << i << "," << B[j - 1] << "): " << A << endl;
j--;
}
}
int main()
{
ifstream fin("bac.txt");
fin >> A >> B;
n = A.length();
m = B.length();
T.resize(n + 1);
for (int i = 0;i <= n;i++)
T[i].resize(m + 1);
COST();
cout << T[n][m].cost << endl << endl;
operatii();
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("sumtri.in");
ofstream fout("sumtri.out");
int n;
fin >> n;
vector<vector<int> > M(n);
for (int i = 0;i < n;i++)
M[i].resize(i + 1);
for (int i = 0;i < n;i++)
for (int j = 0;j <= i;j++)
fin >> M[i][j];
for (int i = n - 2;i >= 0;i--)
for (int j = 0;j <= i;j++)
M[i][j] += max(M[i + 1][j], M[i + 1][j + 1]);
fout << M[0][0];
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("comori.in");
ofstream fout("comori.out");
int n, m;
fin >> n >> m;
vector<vector<int> > M(n + 1, vector<int>(m + 2));
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
fin >> M[i][j];
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
M[i][j] += max(M[i - 1][j], max(M[i - 1][j - 1], M[i - 1][j + 1]));
int maxy = M[n][1];
for (int j = 2;j <= m;j++)
if (maxy < M[n][j])
maxy = M[n][j];
fout << maxy;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
vector<vector<int> > G;
vector<int> extra;
vector<bool> nod, viz, Conex;
int n, m;
void read()
{
ifstream fin("conexidad.in");
fin >> n >> m;
G.resize(n + 1);
extra.resize(n + 1);
nod.resize(n + 1);
viz.resize(n + 1);
Conex.resize(n + 1, true);
Conex[0] = false;
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
nod[x] = true;
nod[y] = true;
}
}
void conex(int start)
{
viz[start] = true;
for (int t : G[start])
if (!viz[t])
conex(t);
}
int main()
{
ofstream fout("conexidad.out");
read();
int nr = 0, k = 0, ok = 1;
vector<pair<int, int> > sol;
for (int i = 1; i <= n; i++)
if (!nod[i])
{
ok = true;
for (int j = 1; j <= n and ok; j++)
if (!nod[j] and i != j)
{
nod[i] = true;
nod[j] = true;
sol.push_back({ i,j });
G[i].push_back(j);
G[j].push_back(i);
extra[i]++;
extra[j]++;
nr++;
ok = false;
}
if (ok)
{
k = i;
ok = 2;
}
}
int min_max = 100;
if (ok == 2)
{
int t = 0;
for (int i = 1; i <= n; i++)
if (min_max > extra[i])
{
min_max = extra[i];
t = i;
}
extra[t]++;
nr++;
sol.push_back({ k,t });
G[k].push_back(t);
G[t].push_back(k);
}
for (int i = 1; i <= n; i++)
{
conex(i);
if (Conex != viz)
{
min_max = 100;
int t = 0;
for (int j = 1; j <= n; j++)
if (min_max > extra[j] and i != j and !viz[j])
{
min_max = extra[j];
t = j;
}
sol.push_back({ i,t });
G[i].push_back(t);
G[t].push_back(i);
extra[i]++;
extra[t]++;
conex(t);
nr++;
viz.clear();
viz.resize(n + 1);
}
}
int extra_max = 1;
for (int i = 1; i <= n; i++)
if (extra_max < extra[i] and extra[i])
extra_max = extra[i];
fout << extra_max << '\n' << nr << '\n';
for (pair<int, int> T : sol)
fout << T.first << " " << T.second << '\n';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int main()
{
ifstream fin("lacusta.in");
ofstream fout("lacusta.out");
int n, m;
fin >> n >> m;
vector<vector<int> > M(n, vector<int>(m)), dp(n, vector<int>(m, 256));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
fin >> M[i][j];
for (int j = 1; j < m; j++)
dp[1][j] = M[0][0] + M[0][j] + M[1][j];
for (int i = 1; i < n; i++)
for (int j = 0;j < m;j++)
{
int miny = M[i][0], t = 0;
for (int k = 1;k < m;k++)
if (miny > M[i][k])
{
miny = M[i][k];
t = k;
}
if (t != j)
dp[i][j] = M[i][j] + M[i - 1][j] + miny;
else
{
for (int k = 1;k < m;k++)
if (miny > M[i][k] and k != t)
miny = M[i][k];
dp[i][j] = M[i][j] + M[i - 1][j] + miny;
}
}
int Miny = M[n - 1][0];
for (int j = 0;j < m;j++)
if (Miny > M[n - 1][j])
Miny = M[n - 1][j];
fout << M[n - 1][m - 1] + Miny;
for (int i = 0;i < n;i++)
{
for (int j = 0;j < m;j++)
cout << dp[i][j] << " ";
cout << endl;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("bac.txt");
vector<vector<bool> > G;
vector<int> lant;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1, vector<bool>(n + 1));
int x, y;
while (fin >> x >> y)
{
G[x][y] = true;
G[y][x] = true;
}
}
void euler(int start)
{
for (int i = 1;i <= n;i++)
if (G[start][i])
{
G[start][i] = false;
G[i][start] = false;
euler(i);
}
lant.push_back(start);
}
int main()
{
read();
euler(1);
for (int i : lant)
cout << i << " ";
}*/
/*#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("euler.in");
ofstream fout("euler.out");
vector<vector<bool> > G;
vector<int> chain;
int n;
void read()
{
fin >> n;
G.resize(n + 1, vector<bool>(n + 1));
int x, y;
while (fin >> x >> y)
G[x][y] = G[y][x] = true;
}
void euler(int start)
{
for (int i = 1;i <= n;i++)
if (G[start][i])
{
G[start][i] = G[i][start] = false;
euler(i);
}
chain.push_back(start);
}
int main()
{
read();
euler(1);
fout << chain.size() << '\n';
for (int i : chain)
fout << i << ' ';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("bac.txt");
vector<vector<int> > G;
vector<pair<int, int> > Grad;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
Grad.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
Grad[y].first++;
Grad[x].second++;
}
}
void print()
{
for (int i = 1;i <= n;i++)
{
cout << i << " : ";
for (int j : G[i])
cout << j << ' ';
cout << '\n';
}
}
void solve()
{
for (int i = 1;i <= n;i++)
cout << i << " : -grad interior : " << Grad[i].first << "\n -grad exterior : " << Grad[i].second << '\n';
}
int main()
{
read();
solve();
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.in");
vector<vector<pair<int, int> > > G;
vector<bool> ales;
vector<int> ciclu;
int n, m, nrm = 0;
void read()
{
fin >> n >> m;
G.resize(n + 1);
ales.resize(m + 1);
int x, y;
while (fin >> x >> y)
{
nrm++;
G[x].push_back({ y,nrm });
G[y].push_back({ x,nrm });
}
}
void euler(int vf)
{
int y, nrm;
while (!G[vf].empty())
{
y = G[vf].back().first;
nrm = G[vf].back().second;
G[vf].pop_back();
if (!ales[nrm])
{
ales[nrm] = 1;
euler(y);
}
}
ciclu.push_back(vf);
}
int main()
{
read();
euler(1);
for (int i : ciclu)
cout << i << ' ';
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("orase.in");
ofstream fout("orase.out");
vector<vector<int> > G;
vector<bool> viz;
vector<int> road;
int n;
void read()
{
fin >> n;
G.resize(n + 1, vector<int>(n + 1));
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
fin >> G[i][j];
}
void euler(int start, int& s)
{
viz[start] = true;
int miny = 1000, t = 0;
for (int i = 1;i <= n;i++)
if (miny > G[start][i] and !viz[i])
{
miny = G[start][i];
t = i;
}
if (t)
euler(t, s);
road.push_back(start);
}
int main()
{
read();
int miny = 1000000, s;
vector<int> real_road;
for (int i = 1;i <= n;i++)
{
viz.clear();
road.clear();
viz.resize(n + 1);
s = 0;
euler(i, s);
s += G[i][road[0]];
for (int i = 0;i < n - 1;i++)
s += G[road[i]][road[i + 1]];
if (miny > s)
{
miny = s;
real_road = road;
}
}
fout << miny;
fout << '\n';
for (int i = n - 1;i >= 0;i--)
fout << real_road[i] << ' ';
fout << real_road[n - 1];
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fin("parc.in");
ofstream fout("parc.out");
vector<vector<int> > G;
vector<int> color;
vector<bool> nrcolor;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
color.resize(n + 1);
nrcolor.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void solve(int start)
{
color[start] = 1;
nrcolor[1] = true;
queue<int> Q;
Q.push(start);
while (!Q.empty())
{
vector<int> used_color;
for (int t : G[Q.front()])
if (!color[t])
Q.push(t);
else
used_color.push_back(color[t]);
for (int i = 1;i <= n;i++)
if (find(used_color.begin(), used_color.end(), i) == used_color.end())
{
color[Q.front()] = i;
nrcolor[i] = true;
break;
}
Q.pop();
}
}
int main()
{
read();
solve(1);
int nr = 0;
for (int i = 1;i <= n;i++)
if (nrcolor[i])
nr++;
fout << nr << '\n';
for (int i = 1;i <= n;i++)
fout << color[i] << ' ';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("cartite.in");
ofstream fout("cartite.out");
vector<vector<int> > M;
vector<int> Viz;
vector<vector<pair<int, int> > > G;
vector<pair<int, int> > v, vmax;
short c;
int n, m;
pair<int, int> cartita;
void read()
{
fin >> c >> n >> m;
fin >> cartita.first >> cartita.second;
M.resize(n + 2, vector<int>(m + 2));
G.resize(n * m + 1);
Viz.resize(n * m + 1);
for (int i = 0; i <= n + 1; i++)
M[i][0] = M[i][m + 1] = -1;
for (int j = 0; j <= m + 1; j++)
M[0][j] = M[n + 1][j] = -1;
int vulpe;
fin >> vulpe;
for (int i = 1; i <= vulpe; i++)
{
int x, y, range;
fin >> x >> y >> range;
M[x][y] = -1;
if (range >= 1)
{
if (x > 0)
M[x - 1][y] = -1;
if (x < n)
M[x + 1][y] = -1;
if (y > 0)
M[x][y - 1] = -1;
if (y < m)
M[x][y + 1] = -1;
}
if (range >= 2)
{
if (x > 1)
M[x - 2][y] = -1;
if (x < n - 1)
M[x + 2][y] = -1;
if (y > 1)
M[x][y - 2] = -1;
if (y < m - 1)
M[x][y + 2] = -1;
}
}
int g;
fin >> g;
for (int i = 1; i <= g; i++)
{
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
G[(x1 - 1) * m + y1].push_back({ x2,y2 });
M[x1][y1] = -2;
M[x2][y2] = -2;
}
}
void print()
{
for (int i = 0; i <= n + 1; i++)
{
for (int j = 0; j <= m + 1; j++)
cout << M[i][j] << " ";
cout << '\n';
}
}
pair<pair<int, int>, int> Lee(pair<int, int> start)
{
queue<pair<int, int> > Q;
Q.push(start);
vector<int> di = { 1,-1,0,0 };
vector<int> dj = { 0,0,1,-1 };
while (!Q.empty())
{
for (int i = 0; i <= 3; i++)
{
if (M[Q.front().first + di[i]][Q.front().second + dj[i]] == -2)
return { {Q.front().first + di[i],Q.front().second + dj[i]},M[Q.front().first][Q.front().second] + 1 };
if (M[Q.front().first + di[i]][Q.front().second + dj[i]] == 0)
{
M[Q.front().first + di[i]][Q.front().second + dj[i]] = M[Q.front().first][Q.front().second] + 1;
Q.push({ Q.front().first + di[i], Q.front().second + dj[i] });
}
}
Q.pop();
}
return { {-1,-1},-1 };
}
void Euler(pair<int, int> start)
{
int cord = (start.first - 1) * m + start.second;
while (!G[cord].empty())
{
int x, y;
x = G[cord].back().first;
y = G[cord].back().second;
G[cord].pop_back();
if (!Viz[cord])
{
Viz[cord] = true;
Euler({ x,y });
}
}
v.push_back(start);
}
void printG()
{
for (int i = 1;i <= n * m;i++)
{
cout << i << " : ";
for (pair<int, int> j : G[i])
cout << j.first << ' ' << j.second << " , ";
cout << '\n';
}
}
int main()
{
read();
if (c == 1)
{
pair<pair<int, int>, int> t = Lee(cartita);
fout << t.first.first << ' ' << t.first.second << ' ' << t.second;
}
else
{
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
{
v.clear();
Euler({ i,j });
if (v.size() > vmax.size())
vmax = v;
}
pair<int, int> k = *vmax.rbegin();
fout << k.first << ' ' << k.second << '\n';
for (pair<int, int> t : vmax)
fout << t.first << ' ' << t.second << '\n';
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G, M;
vector<int> Ext, Int;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
Ext.resize(n + 1);
Int.resize(n + 1);
M.resize(n + 1, vector<int>(n + 1));
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
Ext[x]++;
Int[y]++;
M[x][y] = 1;
}
}
void FW()
{
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (i != j and !M[i][j] and M[i][k] * M[k][j] == 1)
M[i][j] = 1;
}
int main()
{
read();
for (int i = 1;i <= n;i++)
cout << i << " : " << Ext[i] << ' ' << Int[i] << '\n';
FW();
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= n;j++)
cout << M[i][j] << ' ';
cout << '\n';
}
}*/
//Tema
//d) 7
//b) 2
//b) 2
//b) 2
//c) 15
//c) 3
//b) 2
//
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("bac.txt");
int main()
{
int n, P, Q;
fin >> n >> P >> Q;
vector<vector<int> > M(n, vector<int>(n - P + 2)), dp(n, vector<int>(n - Q + 2));
for (int i = 0;i < n;i++)
for (int j = 0;j < n;j++)
fin >> M[i][j];
for (int i = 0;i <= n - P;i++)
for (int j = 0;j <= n - Q;j++)
for (int k = 0;k < P;k++)
for (int t = 0;t < Q;t++)
dp[i][j] += M[k + i][t + j];
int maxy = dp[0][0];
for (int i = 0;i <= n - P;i++)
for (int j = 0;j <= n - Q;j++)
if (maxy < dp[i][j])
maxy = dp[i][j];
cout << maxy;
}*/
/*#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int A, B, C, D;
vector<vector<int> > dp(1005, vector<int>(1005, -1));
queue<pair<int, int> > Q;
bool Ok(int x, int y)
{
return (x >= 0 and y >= 0 and x <= 1000 and y <= 1000 and dp[x][y] == -1);
}
void solve()
{
Q.push({ A,B });
dp[A][B] = 0;
while (!Q.empty() and dp[C][D] == -1)
{
int x, y;
x = Q.front().first;
y = Q.front().second;
Q.pop();
if (Ok(x + y, y))
{
dp[x + y][y] = dp[x][y] + 1;
Q.push({ x + y,y });
}
if (Ok(x - y, y))
{
dp[x - y][y] = dp[x][y] + 1;
Q.push({ x - y,y });
}
if (Ok(y, x))
{
dp[y][x] = dp[x][y] + 1;
Q.push({ y,x });
}
}
}
int main()
{
cin >> A >> B >> C >> D;
solve();
if (dp[C][D] != -1)
cout << dp[C][D];
else
cout << "Imposibile";
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.in");
vector<vector<bool> > M;
vector<int> ctc, viz;
int n, m, nrc = 0;
void read()
{
fin >> n >> m;
int x, y;
M.resize(n + 1, vector<bool>(n + 1));
viz.resize(n + 1);
while (fin >> x >> y)
M[x][y] = true;
}
void FW()
{
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (i != j and !M[i][j] and M[i][k] * M[k][j] == 1)
M[i][j] = true;
}
void CTC()
{
ctc.resize(n + 1);
for (int i = 1;i <= n;i++)
if (!viz[i])
{
nrc++;
viz[i] = nrc;
for (int j = 1;j <= n;j++)
if (M[i][j] and M[j][i])
viz[j] = nrc;
}
}
int main()
{
read();
FW();
CTC();
for (int i = 1;i <= nrc;i++)
{
for (int j = 1;j <= n;j++)
if (viz[j] == i)
cout << j << ' ';
cout << '\n';
}
}*/
//Sortare topologica
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G;
vector<int> viz, Int;
stack<int> S;
int n, m;
void read()
{
fin >> n >> m;
int x, y;
G.resize(n + 1);
viz.resize(n + 1);
Int.resize(n + 1);
while (fin >> x >> y)
{
G[x].push_back(y);
Int[y]++;
}
}
void top_sort()
{
queue<int> Q;
for (int i = 1;i <= n;i++)
if (!Int[i])
Q.push(i);
while (!Q.empty())
{
cout << Q.front() << ' ';
for (int i : G[Q.front()])
{
Int[i]--;
if (!Int[i])
Q.push(i);
}
Q.pop();
}
}
void r_top_sort(int vf)
{
cout << vf << ' ';
viz[vf] = true;
for (int t : G[vf])
{
Int[t]--;
if (!Int[t] and !viz[t])
r_top_sort(t);
}
}
int main()
{
read();
for (int i = 1;i <= n;i++)
if (!Int[i] and !viz[i])
r_top_sort(i);
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G, GT;
vector<int> CTC, viz;
stack<int> S;
int n, m, nrc = 0;
void read()
{
fin >> n >> m;
G.resize(n + 1);
GT.resize(n + 1);
CTC.resize(n + 1);
viz.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
GT[y].push_back(x);
}
}
void print_GT()
{
for (int i = 1;i <= n;i++)
{
cout << i << " : ";
for (int j : GT[i])
cout << j << ' ';
cout << '\n';
}
}
int main()
{
read();
print_GT();
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("topsort.in");
ofstream fout("topsort.out");
vector<vector<int> > G;
vector<int> Int;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
Int.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
Int[y]++;
}
}
void top_sort()
{
queue<int> Q;
for (int i = 1;i <= n;i++)
if (!Int[i])
Q.push(i);
while (!Q.empty())
{
fout << Q.front() << ' ';
for (int t : G[Q.front()])
{
Int[t]--;
if (!Int[t])
Q.push(t);
}
Q.pop();
}
}
int main()
{
read();
top_sort();
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
vector<vector<bool> > G;
vector<bool> viz;
int n, m;
void read()
{
cin >> n >> m;
G.resize(n + 1, vector<bool>(n + 1));
viz.resize(n + 1);
int x, y;
for (int i = 0;i < m;i++)
{
cin >> x >> y;
G[x][y] = true;
}
}
void FW()
{
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (i != j and !G[i][j] and G[i][k] * G[k][j] == 1)
G[i][j] = true;
}
int main()
{
read();
int nrc = 0;
FW();
for (int i = 1;i <= n;i++)
if (!viz[i])
{
nrc++;
viz[i] = true;
for (int j = 1;j <= n;j++)
if (G[i][j] and G[j][i])
viz[j] = true;
}
cout << nrc;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("pm.in");
ofstream fout("pm.out");
vector<vector<int> > G, Gt;
vector<int> Time, Int, sorted;
vector<pair<int, int> > value;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
Gt.resize(n + 1);
Time.resize(n + 1);
Int.resize(n + 1);
value.resize(n + 1);
for (int i = 1;i <= n;i++)
fin >> Time[i];
for (int i = 1;i <= n;i++)
{
int k;
fin >> k;
for (int j = 1;j <= k;j++)
{
int phase;
fin >> phase;
G[phase].push_back(i);
Gt[i].push_back(phase);
Int[i]++;
}
}
}
void top_sort()
{
queue<int> Q;
for (int i = 1;i <= n;i++)
if (!Int[i])
Q.push(i);
while (!Q.empty())
{
sorted.push_back(Q.front());
for (int t : G[Q.front()])
{
Int[t]--;
if (!Int[t])
Q.push(t);
}
Q.pop();
}
}
void distance()
{
vector<int> New_time = Time;
for (int i : sorted)
{
int miny = 0;
for (int j : Gt[i])
if (!miny or miny < New_time[j])
miny = New_time[j];
New_time[i] += miny;
}
int maxy = New_time[1];
for (int i = 2;i <= n;i++)
if (maxy < New_time[i])
maxy = New_time[i];
fout << maxy << '\n';
for (int i = 1;i <= n;i++)
value[i].first = New_time[i] - Time[i];
for (int i = n;i >= 1;i--)
{
int maxy2 = 0;
for (int t : G[i])
if (!maxy2 or maxy2 > value[t].second)
maxy2 = value[t].second;
if (!maxy2)
value[i].second = maxy - Time[i];
else
value[i].second = maxy2 - Time[i];
}
for (int i = 1;i <= n;i++)
fout << value[i].first << ' ' << value[i].second << '\n';
}
int main()
{
read();
top_sort();
distance();
}*/
//Kosaraj
/*#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("graf.in");
vector<vector<int> > G, Gt;
vector<int> viz, CTC;
stack<int> S;
int n, m, nrc = 0;
void read()
{
fin >> n >> m;
G.resize(n + 1);
Gt.resize(n + 1);
viz.resize(n + 1);
CTC.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void dfs(int start)
{
viz[start] = 1;
for (int t : G[start])
if (!viz[t])
dfs(t);
S.push(start);
}
void dfst(int start)
{
viz[start] = 2;
CTC[start] = nrc;
for (int t : Gt[start])
if (viz[t] == 1)
dfst(t);
}
void solve()
{
for (int i = 1;i <= n;i++)
if (viz[i] == 0)
dfs(i);
while (!S.empty())
{
if (viz[S.top()] == 1)
{
nrc++;
dfst(S.top());
}
S.pop();
}
cout << nrc << '\n';
}
void print()
{
if (!S.empty())
{
cout << S.top() << ' ';
S.pop();
print();
}
}
int main()
{
read();
solve();
for (int i = 1;i < n;i++)
{
for (int j = 1;j <= n;j++)
if (CTC[j] == CTC[i])
cout << j << ' ';
cout << '\n';
}
}*/
//Dijkstra
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("dijkstra.in");
#define CV pair<int,int>
#define oo 0x3f3f3f3f
vector<vector<CV> > G;
vector<int> cost, pred;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
cost.resize(n + 1, oo);
pred.resize(n + 1, 0);
int x, y, c;
while (fin >> x >> y >> c)
G[x].push_back({ y,c });
}
void Dijkstra(int start)
{
priority_queue<CV, vector<CV>, greater<CV> > PQ;
PQ.push({ 0,start });
cost[start] = 0;
while (!PQ.empty())
{
int vf = PQ.top().second;
PQ.pop();
for (auto vec : G[vf])
{
int u = vec.first, c = vec.second;
if (cost[u] > cost[vf] + c)
{
cost[u] = cost[vf] + c;
pred[u] = vf;
PQ.push({ cost[u], u });
}
}
}
}
void print()
{
for (int i = 1;i <= n;i++)
cout << cost[i] << ' ';
cout << '\n';
for (int i = 1;i <= n;i++)
cout << pred[i] << ' ';
}
int main()
{
read();
Dijkstra(3);
print();
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define oo 0x3f3f3f3f
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<vector<pair<int, int> > > G;
vector<int> cost;
int n, p;
void read()
{
fin >> n >> p;
G.resize(n + 1);
cost.resize(n + 1, oo);
int x, y, c;
while (fin >> x >> y >> c)
G[x].push_back({ y,c });
}
void Dijkstra()
{
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
PQ.push({ 0,p });
cost[p] = 0;
while (!PQ.empty())
{
for (pair<int, int> t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
PQ.push({ cost[t.first],t.first });
}
PQ.pop();
}
}
int main()
{
read();
Dijkstra();
for (int i = 1;i <= n;i++)
if (cost[i] == oo)
fout << -1 << ' ';
else
fout << cost[i] << ' ';
}*/
/*#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define oo 0x3f3f3f3f
#define PAIR pair<int,int>
vector<vector<PAIR> > G;
vector<int> cost;
int n, m;
void read()
{
cin >> n >> m;
G.resize(n + 1);
int x, y, c;
for (int i = 0;i < m;i++)
{
cin >> x >> y >> c;
G[x].push_back({ y,c });
}
}
void Dijkstra(int start)
{
priority_queue<PAIR, vector<PAIR>, greater<PAIR> > PQ;
cost.clear();
cost.resize(n + 1, oo);
PQ.push({ 0,start });
cost[start] = 0;
while (!PQ.empty())
{
for (PAIR t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
PQ.push({ cost[t.first],t.first });
}
PQ.pop();
}
}
int main()
{
read();
int nr = 0;
for (int i = 1;i <= n;i++)
{
Dijkstra(i);
for (PAIR j : G[i])
if (j.second == cost[j.first])
nr++;
}
cout << nr;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("firma.in");
ofstream fout("firma.out");
#define oo 0x3f3f3f3f
#define Pair pair<int,int>
vector<vector<Pair> > G;
vector<int> cost;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
int x, y, c;
while (fin >> x >> y >> c)
{
G[x].push_back({ y,c });
G[y].push_back({ x,c });
}
}
void Dijkstra(int start)
{
cost.clear();
cost.resize(n + 1, oo);
priority_queue<Pair, vector<Pair>, greater<Pair> > PQ;
cost[start] = 0;
PQ.push({ 0,start });
while (!PQ.empty())
{
for (Pair t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
PQ.push({ cost[t.first],t.first });
}
PQ.pop();
}
}
int main()
{
read();
int smin = oo, nod = 0;
for (int i = 1;i <= n;i++)
{
Dijkstra(i);
int s = cost[1];
for (int i = 2;i <= n;i++)
s += cost[i];
if (smin > s)
{
smin = s;
nod = i;
}
}
fout << nod;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("parc.in");
ofstream fout("parc.out");
#define oo 0x3f3f3f3f
#define Pair pair<int,int>
vector<vector<Pair> > G;
vector<int> cost, gate;
int n, m, C, g;
void read()
{
fin >> n >> m >> C;
G.resize(n + 1);
int x, y, c;
for (int i = 0;i < m;i++)
{
fin >> x >> y >> c;
G[x].push_back({ y,c });
G[y].push_back({ x,c });
}
fin >> g;
gate.resize(g);
for (int i = 0;i < g;i++)
fin >> gate[i];
}
void Dijkstra(int start)
{
cost.clear();
cost.resize(n + 1, oo);
cost[start] = 0;
priority_queue<Pair, vector<Pair>, greater<Pair> > PQ;
PQ.push({ 0,start });
while (!PQ.empty())
{
for (Pair t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
PQ.push({ cost[t.first],t.first });
}
PQ.pop();
}
}
int main()
{
read();
int dmin = oo, poarta = 0;
for (int i = 0;i < g;i++)
{
Dijkstra(gate[i]);
int d = cost[C];
if (dmin > d)
{
dmin = d;
poarta = gate[i];
}
}
fout << poarta;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.in");
#define oo 0x3f3f3f3f
#define Pair pair<int,int>
vector<vector<Pair> > G;
vector<int> cost, pred;
int n, m;
void read()
{
fin >> n >> m;
G.resize(n + 1);
cost.resize(n + 1, oo);
pred.resize(n + 1);
int x, y, c;
while (fin >> x >> y >> c)
G[x].push_back({ y,c });
}
void Dijkstra(int start)
{
priority_queue<Pair, vector<Pair>, greater<Pair> > PQ;
cost[start] = 0;
PQ.push({ 0,start });
while (!PQ.empty())
{
for (Pair t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
pred[t.first] = PQ.top().second;
PQ.push({ cost[t.first],t.first });
}
PQ.pop();
}
}
void print_road(int x)
{
if (pred[x])
print_road(pred[x]);
cout << x << ' ';
}
int main()
{
read();
Dijkstra(3);
for (int i = 1;i <= n;i++)
if (cost[i] != oo)
{
print_road(i);
cout << '\n';
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("arbore.in");
vector<int> T;
int n, X, Y;
void read()
{
fin >> n >> X >> Y;
T.resize(n + 1);
int x, y;
while (fin >> x >> y)
T[y] = x;
}
void solve_a()
{
for (int i = 1;i <= n;i++)
if (!T[i])
{
cout << i;
return;
}
}
void solve_b()
{
for (int i = 1;i <= n;i++)
if (find(T.begin(), T.end(), i) == T.end())
cout << i << ' ';
}
void solve_c()
{
for (int i = 1;i <= n;i++)
if (T[i] == X)
cout << i << ' ';
}
void solve_d()
{
for (int i = 1;i <= n;i++)
{
int t = T[i];
while (t)
{
if (t == X)
{
cout << i << ' ';
break;
}
t = T[t];
}
}
}
void solve_e(int start)
{
if (start)
{
solve_e(T[start]);
cout << start << ' ';
}
}
void solve_f(int start)
{
if (start)
{
solve_f(T[start]);
cout << start << ' ';
}
}
void solve_g(int start)
{
if (start != 0)
{
solve_g(T[start]);
cout << start << ' ';
}
}
void solve_G(int start)
{
if (start != 0)
{
cout << start << ' ';
solve_G(T[start]);
}
}
void solveGg()
{
solve_G(X);
cout << "\b\b";
solve_g(Y);
}
int get_level(int start)
{
if (start)
return get_level(T[start]) + 1;
return 0;
}
void level()
{
for (int i = 1;i <= n;i++)
cout << get_level(T[i]) << ' ';
}
int main()
{
read();
level();
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("smallworld.in");
ofstream fout("smallworld.out");
vector<vector<int> > G;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
int get_road(int start)
{
vector<int> road(n + 1);
queue<int> Q;
Q.push(start);
road[start] = 1;
while (!Q.empty())
{
for (int t : G[Q.front()])
if (!road[t])
{
road[t] = road[Q.front()] + 1;
Q.push(t);
}
Q.pop();
}
int maxy = road[1];
for (int i = 2;i <= n;i++)
if (maxy < road[i])
maxy = road[i];
return maxy;
}
int main()
{
read();
for (int i = 1;i <= n;i++)
fout << get_road(i) - 1 << '\n';
}*/
//Kruskal
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("cruscal.in");
vector<pair<int, pair<int, int> > > Edges;
vector<int> P, Height, MST;//minimum spanning tree (MST)
int n, m, weight;
void read()
{
fin >> n >> m;
P.resize(n + 1);
Height.resize(n + 1);
for (int i = 1;i <= n;i++)
P[i] = i;
int x, y, c;
while (fin >> x >> y >> c)
Edges.push_back({ c,{x,y} });
}
int get_P(int x)
{
if (P[x] == x)
return x;
return get_P(P[x]);
}
void Kruskal()
{
int M = 0, Pfirst, Psecond;
while (MST.size() < n - 1)
{
Pfirst = get_P(Edges[M].second.first);
Psecond = get_P(Edges[M].second.second);
if (Pfirst != Psecond)
{
MST.push_back(M);
if (Height[Pfirst] > Height[Psecond])
P[Psecond] = Pfirst;
else
P[Pfirst] = Psecond;
if (Height[Pfirst] == Height[Psecond])
Height[Psecond]++;
}
M++;
}
}
void print()
{
for (int t : MST)
weight += Edges[t].first;
cout << weight << '\n';
for (int t : MST)
{
cout << '(' << Edges[t].second.first << ',' << Edges[t].second.second << ") ";
}
}
int main()
{
read();
sort(Edges.begin(), Edges.end());
Kruskal();
print();
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("kruskal.in");
ofstream fout("kruskal.out");
vector<pair<int, pair<int, int> > > Edges;
vector<int> P, Height, MST;
int n, m, weight = 0;
void read()
{
fin >> n >> m;
P.resize(n + 1);
Height.resize(n + 1);
for (int i = 1;i <= n;i++)
P[i] = i;
int x, y, c;
while (fin >> x >> y >> c)
Edges.push_back({ c,{x,y} });
}
int getP(int x)
{
if (P[x] == x)
return x;
return getP(P[x]);
}
void kruskal()
{
int M = 0, Pfirst, Psecond;
while (MST.size() < n - 1)
{
Pfirst = getP(Edges[M].second.first);
Psecond = getP(Edges[M].second.second);
if (Pfirst != Psecond)
{
MST.push_back(M);
if (Height[Pfirst] > Height[Psecond])
P[Psecond] = Pfirst;
else
P[Pfirst] = Psecond;
if (Height[Pfirst] == Height[Psecond])
Height[Psecond]++;
}
M++;
}
}
void print()
{
for (int t : MST)
weight += Edges[t].first;
fout << weight << '\n';
for (int t : MST)
fout << Edges[t].second.first << ' ' << Edges[t].second.second << '\n';
}
int main()
{
read();
sort(Edges.begin(), Edges.end());
kruskal();
print();
}*/
//Prim
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("kruskal.in");
ofstream fout("kruskal.out");
#define oo 0x3f3f3f3f
#define Vecin pair<int,int>
vector<vector<Vecin> > G;
vector<int> cost, P;
vector<bool> Viz;
int n, m, start = 3;
void read()
{
fin >> n >> m;
G.resize(n + 1);
P.resize(n + 1, -1);
cost.resize(n + 1, oo);
Viz.resize(n + 1);
int x, y, c;
while (fin >> x >> y >> c)
{
G[x].push_back({ y,c });
G[y].push_back({ x,c });
}
}
void Prim()
{
priority_queue<Vecin, vector<Vecin>, greater<Vecin> > PQ;
PQ.push({ 0,start });
cost[start] = 0;
while (!PQ.empty())
{
int v = PQ.top().second;
PQ.pop();
if (!Viz[v])
{
Viz[v] = true;
for (auto x : G[v])
{
int vec = x.first, c = x.second;
if (!Viz[vec] and cost[vec] > c)
{
cost[vec] = c;
PQ.push({ c,vec });
P[vec] = v;
}
}
}
}
}
void write()
{
for (int i = 1;i <= n;i++)
if (i != start)
cout << '(' << P[i] << ',' << i << ") ";
}
void print()
{
for (int i = 1;i <= n;i++)
if (i != start)
fout << P[i] << ' ' << i;
}
int main()
{
read();
Prim();
write();
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("urgenta.in");
ofstream fout("urgenta.out");
int n, m, k;
vector<pair<int, pair<int, int> > > Edges;
vector<int> Height, MST, P;
vector<bool> no_print;
void read()
{
fin >> n >> m >> k;
P.resize(n + 1);
Height.resize(n + 1);
no_print.resize(m);
for (int i = 1;i <= n;i++)
P[i] = i;
int x, y, c;
while (fin >> x >> y >> c)
Edges.push_back({ c,{x,y} });
}
int getP(int x)
{
if (P[x] == x)
return x;
return getP(P[x]);
}
void Kruskal()
{
int M = 0, Pfirst, Psecond, component = n;
while (MST.size() < n - 1 and component > k)
{
Pfirst = getP(Edges[M].second.first);
Psecond = getP(Edges[M].second.second);
if (Pfirst != Psecond)
{
MST.push_back(M);
no_print[M] = true;
if (Height[Pfirst] > Height[Psecond])
P[Psecond] = Pfirst;
else
P[Pfirst] = Psecond;
if (Height[Pfirst] == Height[Psecond])
Height[Psecond]++;
component--;
}
M++;
}
}
void print()
{
int sz = Edges.size(), gravmax = 0;
for (int i = 0;i < sz;i++)
if (!no_print[i])
gravmax += Edges[i].first;
fout << gravmax << '\n' << m - MST.size() << '\n';
for (int i = 0;i < sz;i++)
if (!no_print[i])
fout << Edges[i].second.first << ' ' << Edges[i].second.second << '\n';
}
int main()
{
read();
sort(Edges.begin(), Edges.end());
Kruskal();
print();
}*/
//Prim cost minim
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("graf.txt");
#define oo 0x3f3f3f3f
#define Vecin pair<int,int>
vector<vector<Vecin> > G;
vector<int> cost, P;
vector<bool> Viz;
int n, m, start = 3, cmin = 0;
void read()
{
fin >> n >> m;
G.resize(n + 1);
P.resize(n + 1, -1);
cost.resize(n + 1, oo);
Viz.resize(n + 1);
int x, y, c;
while (fin >> x >> y >> c)
{
G[x].push_back({ y,c });
G[y].push_back({ x,c });
}
}
void Prim()
{
priority_queue<Vecin, vector<Vecin>, greater<Vecin> > PQ;
PQ.push({ 0,start });
cost[start] = 0;
while (!PQ.empty())
{
int v = PQ.top().second;
PQ.pop();
if (!Viz[v])
{
Viz[v] = true;
for (pair<int, int> x : G[v])
{
int vec = x.first, c = x.second;
if (!Viz[vec] and cost[vec] > c)
{
if (cost[vec] != oo)
cmin -= cost[vec];
cmin += c;
cost[vec] = c;
PQ.push({ c,vec });
P[vec] = v;
}
}
}
}
}
void write()
{
cout << cmin << '\n';
for (int i = 1; i <= n; i++)
if (i != start)
cout << '(' << P[i] << ',' << i << ") ";
}
int main()
{
read();
Prim();
write();
}*/
//Exercitii
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream fin("harta3.in");
ofstream fout("harta3.out");
#define Punct pair<int,int>
vector<pair<float, Punct> > Edges;
vector<int> MST, P, Height;
vector<Punct> v;
int n;
float Weight = 0;
void read()
{
fin >> n;
v.resize(n);
P.resize(n + 1);
Height.resize(n + 1);
for (int i = 1;i <= n;i++)
P[i] = i;
for (int i = 0;i < n;i++)
fin >> v[i].first >> v[i].second;
for (int i = 0;i < n - 1;i++)
for (int j = i + 1;j < n;j++)
{
float cost = sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
Edges.push_back({ cost,{i + 1,j + 1} });
}
}
int get_Parent(int x)
{
if (P[x] == x)
return x;
return get_Parent(P[x]);
}
void Kruskal()
{
int M = 0, Pfirst, Psecond;
while (MST.size() < n - 1)
{
Pfirst = get_Parent(Edges[M].second.first);
Psecond = get_Parent(Edges[M].second.second);
if (Pfirst != Psecond)
{
MST.push_back(M);
if (Height[Pfirst] > Height[Psecond])
P[Psecond] = Pfirst;
else
P[Pfirst] = Psecond;
if (Height[Pfirst] == Height[Psecond])
Height[Psecond]++;
Weight += Edges[M].first;
}
M++;
}
}
int main()
{
read();
sort(Edges.begin(), Edges.end());
Kruskal();
fout << Weight;
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("zapada.in");
ofstream fout("zapada.out");
vector<pair<pair<int, bool>, pair<int, int> > > Edges;
vector<int> P, MST, Height;
int n, m, Weight = 0;
bool CRT(pair<pair<int, bool>, pair<int, int> > a, pair<pair<int, bool>, pair<int, int> > b)
{
if (a.first.second == b.first.second)
return a.first.first < b.first.first;
return a.first.second > b.first.second;
}
void read()
{
fin >> n >> m;
P.resize(n + 1);
Height.resize(n + 1);
for (int i = 1;i <= n;i++)
P[i] = i;
for (int i = 0;i < m;i++)
{
int x, y, c;
fin >> x >> y >> c;
Edges.push_back({ {c,0},{x,y} });
}
int k;
fin >> k;
for (int i = 1;i <= k;i++)
{
int x;
fin >> x;
Edges[x - 1].first.second = true;
}
}
int get_Parent(int x)
{
if (P[x] == x)
return x;
return get_Parent(P[x]);
}
void Kruskal()
{
int M = 0, Pfirst, Psecond;
while (M < m)
{
Pfirst = get_Parent(Edges[M].second.first);
Psecond = get_Parent(Edges[M].second.second);
if (Pfirst != Psecond)
{
MST.push_back(M);
if (Height[Pfirst] > Height[Psecond])
P[Psecond] = Pfirst;
else
P[Pfirst] = Psecond;
if (Height[Pfirst] == Height[Psecond])
Height[Psecond]++;
Weight += Edges[M].first.first;
}
M++;
}
}
int main()
{
read();
sort(Edges.begin(), Edges.end(), CRT);
Kruskal();
fout << Weight;
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fin("vacanta2020.in");
ofstream fout("vacanta2020.out");
#define Pair pair<int,int>
#define oo 0x3f3f3f3f
vector<vector<Pair> > G;
vector<int> cost, pred, v;
int n, m, k;
bool CRT(int a, int b)
{
return a > b;
}
void read()
{
fin >> n >> m >> k;
G.resize(n + 1);
pred.resize(n + 1);
cost.resize(n + 1, oo);
int x, y, c;
while (fin >> x >> y >> c)
{
G[x].push_back({ y,c });
G[y].push_back({ x,c });
}
}
void Dijkstra()
{
priority_queue<Pair, vector<Pair>, greater<Pair> > PQ;
PQ.push({ 0,1 });
cost[1] = 0;
while (!PQ.empty())
{
for (Pair t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
PQ.push({ cost[t.first] , t.first });
pred[t.first] = PQ.top().second;
}
PQ.pop();
}
}
void get_v(int x, int i)
{
if (pred[x])
{
get_v(pred[x], i);
for (Pair t : G[i])
if (t.first == x)
{
v.push_back(t.second);
break;
}
}
else
for (Pair t : G[i])
if (t.first == x)
{
v.push_back(t.second);
break;
}
}
int main()
{
read();
Dijkstra();
for (int i = 2;i <= n;i++)
{
v.clear();
get_v(i, i);
sort(v.begin(), v.end(), CRT);
int sz = v.size(), s = 0;
for (int j = k;j < sz;j++)
s += v[j];
cost[i] = s;
}
for (int i = 1;i <= n;i++)
fout << cost[i] << ' ';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream fin("elicoptere.in");
ofstream fout("elicoptere.out");
bool CRT(pair<double, pair<int, int> > a, pair<double, pair<int, int> > b)
{
return a.first < b.first;
}
vector<pair<double, pair<int, int> > > Edges;
vector<pair<pair<pair<int, int>, pair<int, int>>, pair<int, int> > > v;
vector<int> P, Height, MST;
short V;
int n, k;
double Distance = 0;
void read()
{
fin >> V >> n >> k;
P.resize(n + 1);
Height.resize(n + 1);
for (int i = 1;i <= n;i++)
P[i] = i;
for (int i = 1;i <= n;i++)
{
int x1, x2, x3, y1, y2, y3;
fin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
v.push_back({ {{x1,y1},{x2,y2} }, { x3,y3 } });
}
for (int i = 0;i < n;i++)
for (int j = i + 1;j < n;j++)
{
int xi1 = v[i].first.first.first, yi1 = v[i].first.first.second;
int xj1 = v[j].first.first.first, yj1 = v[j].first.first.second;
int xi2 = v[i].first.second.first, yi2 = v[i].first.second.second;
int xj2 = v[j].first.second.first, yj2 = v[j].first.second.second;
int xi3 = v[i].second.first, yi3 = v[i].second.second;
int xj3 = v[j].second.first, yj3 = v[j].second.second;
double cost11 = abs(xi1 - xj1) + abs(yi1 - yj1);
double cost12 = abs(xi1 - xj2) + abs(yi1 - yj2);
double cost13 = abs(xi1 - xj3) + abs(yi1 - yj3);
double cost21 = abs(xi2 - xj1) + abs(yi2 - yj1);
double cost22 = abs(xi2 - xj2) + abs(yi2 - yj2);
double cost23 = abs(xi2 - xj3) + abs(yi2 - yj3);
double cost31 = abs(xi3 - xj1) + abs(yi3 - yj1);
double cost32 = abs(xi3 - xj2) + abs(yi3 - yj2);
double cost33 = abs(xi3 - xj3) + abs(yi3 - yj3);
if (cost11 > cost12)
cost11 = cost12;
if (cost11 > cost13)
cost11 = cost13;
if (cost11 > cost21)
cost11 = cost21;
if (cost11 > cost22)
cost11 = cost22;
if (cost11 > cost23)
cost11 = cost23;
if (cost11 > cost31)
cost11 = cost31;
if (cost11 > cost32)
cost11 = cost32;
if (cost11 > cost33)
cost11 = cost33;
Edges.push_back({ cost11,{i + 1,j + 1} });
}
}
int getP(int x)
{
if (P[x] == x)
return x;
return getP(P[x]);
}
void Kruskal()
{
int M = 0, Pfirst, Psecond;
while (MST.size() < n - 1)
{
Pfirst = getP(Edges[M].second.first);
Psecond = getP(Edges[M].second.second);
if (Pfirst != Psecond)
{
MST.push_back(M);
Distance += Edges[M].first;
if (Height[Pfirst] > Height[Psecond])
P[Psecond] = Pfirst;
else
P[Pfirst] = Psecond;
if (Height[Pfirst] == Height[Psecond])
Height[Psecond]++;
}
M++;
}
}
int get_v1()
{
int nr = 0;
for (int t : MST)
{
int x = Edges[t].second.first, y = Edges[t].second.second;
if (k >= Edges[t].first)
nr++;
}
return nr;
}
vector<bool> viz;
vector<vector<int> > G;
void dfs(int x, int& nr)
{
viz[x] = true;
nr++;
for (int t : G[x])
if (!viz[t])
{
dfs(t, nr);
}
}
int get_v2()
{
int s = 0;
G.resize(n + 1);
viz.resize(n + 1);
for (int t : MST)
if (k >= Edges[t].first)
{
G[Edges[t].second.first].push_back(Edges[t].second.second);
G[Edges[t].second.second].push_back(Edges[t].second.first);
}
for (int t : MST)
if (!viz[Edges[t].second.first] and k >= Edges[t].first)
{
int nr = 0;
dfs(t, nr);
s += nr * (nr - 1) / 2;
}
return s;
}
int main()
{
read();
sort(Edges.begin(), Edges.end(), CRT);
Kruskal();
if (V == 1)
fout << get_v1();
else
if (V == 2)
fout << get_v2();
}*/
/*#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define Pair pair<int,int>
#define oo 0x3f3f3f3f
vector<vector<Pair> > G;
vector<int> road, cost;
short c;
int n, m;
void read()
{
cin >> c >> n >> m;
G.resize(n + 1);
road.resize(n + 1, oo);
int x, y, d;
for (int i = 1;i <= m;i++)
{
cin >> x >> y >> d;
G[y].push_back({ x,d });
}
}
void Dijkstra(int start)
{
cost.clear();
cost.resize(n + 1, oo);
priority_queue<Pair, vector<Pair>, greater<Pair> > PQ;
PQ.push({ 0,start });
cost[start] = 0;
while (!PQ.empty())
{
for (Pair t : G[PQ.top().second])
if (cost[t.first] > cost[PQ.top().second] + t.second)
{
cost[t.first] = cost[PQ.top().second] + t.second;
PQ.push({ cost[t.first],t.first });
}
PQ.pop();
}
}
int main()
{
read();
vector<int> resedinta;
for (int i = 1;i <= n;i++)
{
Dijkstra(i);
bool ok = true;
for (int j = 1;j <= n and ok;j++)
if (cost[j] == oo)
ok = false;
if (ok)
{
resedinta.push_back(i);
for (int j = 1;j <= n;j++)
if (road[j] > cost[j])
road[j] = cost[j];
}
}
if (c == 1)
for (int t : resedinta)
cout << t << ' ';
else
for (int i = 1;i <= n;i++)
cout << road[i] << ' ';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.txt");
vector<vector<int> > G;
vector<int> nivel;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
nivel.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int x, int niv)
{
nivel[x] = niv;
for (int vec : G[x])
if (!nivel[vec])
dfs(vec, niv + 1);
}
int main()
{
read();
dfs(1, 1);
for (int i = 1;i <= n;i++)
cout << i << " : " << nivel[i] << '\n';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.txt");
vector<vector<int> > G;
vector<int> nivel;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
nivel.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int x, int niv)
{
nivel[x] = niv;
for (int vec : G[x])
if (!nivel[vec])
dfs(vec, niv + 1);
}
int main()
{
read();
dfs(1, 1);
for (int i = 1;i <= n;i++)
cout << i << " : " << nivel[i] << '\n';
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.txt");
vector<vector<int> > G;
vector<int> nivel, tata;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
tata.resize(n + 1);
nivel.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int x, int niv)
{
nivel[x] = niv;
for (int vec : G[x])
if (!nivel[vec])
{
tata[vec] = x;
dfs(vec, niv + 1);
}
}
bool is_leaf(int x)
{
for (int i = 1;i <= n;i++)
if (tata[i] == x)
return 0;
return 1;
}
void print_chain(int x)
{
if (x)
{
print_chain(tata[x]);
cout << x << ' ';
}
}
int main()
{
read();
dfs(1, 1);
for (int i = 1;i <= n;i++)
cout << i << " : " << nivel[i] << '\n';
cout << '\n';
for (int i = 1;i <= n;i++)
cout << i << " : " << tata[i] << '\n';
cout << endl;
for (int i = 1;i <= n;i++)
if (is_leaf(i))
{
print_chain(i);
cout << endl;
}
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.txt");
vector<vector<int> > G;
vector<int> nivel, v;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
v.resize(n + 1);
nivel.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int x, int niv)
{
nivel[x] = niv;
v[niv] = x;
for (int i = 1;i <= niv;i++)
cout << v[i] << ' ';
cout << endl;
for (int vec : G[x])
if (!nivel[vec])
dfs(vec, niv + 1);
}
int main()
{
read();
dfs(1, 1);
}*/
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("graf.txt");
vector<vector<int> > G;
vector<int> nivel, v;
int n;
void read()
{
fin >> n;
G.resize(n + 1);
v.resize(n + 1);
nivel.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void dfs(int x, int niv)
{
nivel[x] = niv;
v[niv] = x;
for (int vec : G[x])
if (!nivel[vec])
dfs(vec, niv + 1);
for (int i = 1;i <= niv;i++)
cout << v[i] << ' ';
cout << endl;
}
int main()
{
read();
dfs(1, 1);
}*/
//Pointers
/*#include<iostream>
using namespace std;
int n;
int* V;
int* find(int* p, int x)
{
if (*p == x)
return p;
if (p - V == n)
return 0;
return find(p + 1, x);
}
int main()
{
cin >> n;
V = new int[n];
for (int* p = V;p - V < n;p++)
cin >> *p;
cout << find(V, 12) - V;
}*/
//Tema
/*#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("sediu.in");
ofstream fout("sediu.out");
vector<vector<int> > G;
vector<int> level, vf;
int n, minlvl, maxlvl;
void read()
{
fin >> n;
minlvl = n;
G.resize(n + 1);
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int x, int lvl)
{
level[x] = lvl;
if (maxlvl < lvl)
maxlvl = lvl;
for (int t : G[x])
if (!level[t])
bfs(t, lvl + 1);
}
int main()
{
read();
for (int i = 1;i <= n;i++)
{
maxlvl = 0;
level.clear();
level.resize(n + 1);
bfs(i, 1);
if (minlvl > maxlvl - 1)
{
minlvl = maxlvl - 1;
vf.clear();
vf.push_back(i);
}
else
if (minlvl == maxlvl)
vf.push_back(i);
}
fout << minlvl << ' ' << vf.size() << '\n';
for (int i : vf)
fout << i << ' ';
}*/
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("asmax.in");
ofstream fout("asmax.out");
vector<vector<int> > G;
vector<int> v, level, chain;
int n, smax = 0;
void read()
{
fin >> n;
G.resize(n + 1);
v.resize(n + 1);
level.resize(n + 1);
chain.resize(n + 1);
for (int i = 1;i <= n;i++)
fin >> v[i];
int x, y;
while (fin >> x >> y)
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void bfs(int x,int lvl)
{
level[x] = lvl;
chain[lvl] = x;
for (int k = 1;k < lvl;k++)
{
int s = 0;
for (int i = k;i <= lvl;i++)
s += v[i];
if (smax < s)
smax = s;
}
for (int t : G[x])
if (!level[t])
bfs(t, lvl + 1);
}
int main()
{
read();
bfs(1, 1);
fout << smax;
}
Spike Dog Sp1k3C