# include <bits/stdc++.h>

using namespace std;

int t, A, B;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> t;
	while (t --){
		cin >> A >> B;
		for (int i = 0; i < min(A, B); ++ i)
			cout << "01";
		for (int i = 0; i < abs(A - B); ++ i)
			cout << (A < B ? 1 : 0);
		cout << '\n';
	}

	return 0;
}

# include <bits/stdc++.h>

using namespace std;

int t, n;
string S;
long long ans;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> t;
	while (t --){
		cin >> n >> S, ans = n;
		for (int i = 1; i < n; ++ i)
			if (S[i] != S[i - 1])
				ans += i;
		cout << ans << '\n';
	}

	return 0;
}

//In the name of God
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 100;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n, t, a[maxn];
long long ps[maxn];

int main(){
	fast_io;
	
	cin >> t;
	while(t--){
		cin >> n;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			ps[i] = ps[i - 1] + a[i];
		}
		if(ps[n] != 0){
			cout << "No\n";
			continue;
		}
		bool ok = 1;
		for(int i = 1; i <= n; i++){
			if(ps[i] < 0) ok = 0;
		}
		bool visited_zero = 0;
		for(int i = 1; i <= n; i++){
			if(ps[i] == 0) visited_zero = 1;
			else if(visited_zero) ok = 0;
		}
		if(ok) cout << "Yes\n";
		else cout << "No\n";
	}
	
	return 0;
}

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int t, n, l[N], r[N], ans;
vector <int> adj[N];

ll DFS(int v){
	ll sum = 0;
	for (int u : adj[v]){
		sum += DFS(u);
	}
	if (sum < ll(l[v])){
		++ ans;
		return r[v];
	}
	return min(ll(r[v]), sum);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> t;
	while (t --){
		cin >> n;
		for (int i = 2; i <= n; ++ i){
			int par;
			cin >> par;
			adj[par].push_back(i);
		}
		for (int i = 1; i <= n; ++ i){
			cin >> l[i] >> r[i];
		}
		ans = 0;
		DFS(1);
		cout << ans << "\n";
		for (int i = 1; i <= n; ++ i){
			adj[i].clear();
		}
	}

	return 0;
}

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, d[N], dist[N];
priority_queue <pair <int, int> > pq;
vector <int> adj[N];
bool mark[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	fill(dist, dist + n + 1, m);
	while (m --){
		int v, u;
		cin >> v >> u;
		adj[u].push_back(v);
		++ d[v];
	}
	dist[n] = 0;
	pq.push({0, n});
	while (!pq.empty()){
		int v = pq.top().second;
		pq.pop();
		if (mark[v])
			continue;
		mark[v] = true;
		for (int u : adj[v]){
			if (dist[v] + d[u] < dist[u]){
				dist[u] = dist[v] + d[u];
				pq.push({- dist[u], u});
			}
			-- d[u];
		}
	}
	cout << dist[1] << '\n';

	return 0;
}

It can be proven that a permutation is Decinc if and only if it's $$$3412$$$-avoiding and $$$2143$$$-avoiding.

# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 10;
 
int n, a[N], dp[N], pd[N], f[N];
long long ans;
 
inline void upd(int i){
	if (n < i)
		return;
	int inc = 0, dec = n + 1;
	if (pd[i - 1] < a[i])
		inc = max(inc, a[i - 1]);
	if (a[i - 1] < a[i])
		inc = max(inc, dp[i - 1]);
	if (a[i] < dp[i - 1])
		dec = min(dec, a[i - 1]);
	if (a[i] < a[i - 1])
		dec = min(dec, pd[i - 1]);
	if (inc == dp[i] && dec == pd[i])
		return;
	dp[i] = inc, pd[i] = dec;
	f[i] = 0;
	if (dec <= n || inc){
		upd(i + 1);
		f[i] = f[i + 1] + 1;
	}
	return;
}
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
	cin >> n;
	for (int i = 1; i <= n; ++ i)
		cin >> a[i];
	for (int i = n; 1 <= i; -- i){
		dp[i] = n + 1;
		pd[i] = 0;
		upd(i + 1);
		f[i] = f[i + 1] + 1;
		ans += f[i];
	}
	cout << ans << '\n';
 
	return 0;
}

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, a[N], min_r[N], fen[N];
long long ans;
stack <int> sk;
vector <int> vec[2][N];

void mofen(int pos, int val){
	for (pos += 5; pos < N; pos += pos & - pos)
		fen[pos] = min(fen[pos], val);
}
int gefen(int pos){
	int res = n + 1;
	for (pos += 5; 0 < pos; pos -= pos & - pos)
		res = min(res, fen[pos]);
	return res;
}

void find_3412(){
	fill(fen, fen + n + 10, n + 1);
	while (!sk.empty())
		sk.pop();
	for (int i = 1; i <= n; ++ i){
		while (!sk.empty() && a[i] < a[sk.top()])
			sk.pop();
		if (!sk.empty())
			vec[0][sk.top()].push_back(i);
		sk.push(i);
	}
	while (!sk.empty())
		sk.pop();
	for (int i = n; 1 <= i; -- i){
		while (!sk.empty() && a[sk.top()] < a[i])
			sk.pop();
		if (!sk.empty())
			vec[1][sk.top()].push_back(i);
		sk.push(i);
	}
	for (int i = n; 1 <= i; -- i){
		for (int ind : vec[0][i])
			mofen(a[ind], ind);
		for (int ind : vec[1][i])
			min_r[ind] = min(min_r[ind], gefen(a[ind] - 1));
		vec[0][i].clear(), vec[1][i].clear();
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++ i)
		cin >> a[i];
	fill(min_r, min_r + n + 2, n + 1);
	find_3412();
	for (int i = 1; i <= n; ++ i)
		a[i] = n + 1 - a[i];
	find_3412();
	for (int i = n; 1 <= i; -- i){
		min_r[i] = min(min_r[i], min_r[i + 1]);
		ans += min_r[i] - i;
	}
	cout << ans << '\n';

	return 0;
}

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

struct cost{
	int c[2][2];
	cost(){
		memset(c, 0, sizeof c);
	}
};

cost cst[2][2];

int n, a[maxn], dp[maxn], cnl[maxn], cnr[maxn];
ll s, ans, ans2;
cost seg[maxn << 2];

inline cost mrg(cost l, cost r){
	cost mid;
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			mid.c[i][j] = min(r.c[i][0] + l.c[0][j], r.c[i][1] + l.c[1][j]);
		}
	}
	return mid;
}

void bld(int id, int s, int e){
	if(e - s == 1){
		seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
		return;
	}
	int mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	seg[id] = mrg(seg[lc], seg[rc]);
	return;
}

void upd(int id, int s, int e, int l, int r){
	if(r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id] = cst[int(cnl[s] > 0)][int(cnr[s] > 0)];
		return;
	}
	int mid = (s + e) >> 1;
	upd(lc, s, mid, l, r);
	upd(rc, mid, e, l, r);
	seg[id] = mrg(seg[lc], seg[rc]);
	return;
}
cost get(int id, int s, int e, int l, int r){
	if(r <= s || e <= l) return cost();
	if(l <= s && e <= r) return seg[id];
	int mid = (s + e) >> 1;
	return mrg(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}

int main(){
	fast_io;
	srand(time(NULL));
	
	cst[0][0].c[0][0] = cst[0][0].c[1][1] = 0;
	cst[0][0].c[0][1] = cst[0][0].c[1][0] = inf;
	
	cst[0][1].c[1][0] = cst[0][1].c[1][1] = 1;
	cst[0][1].c[0][0] = 0;
	cst[0][1].c[0][1] = inf;
	
	cst[1][0].c[0][1] = cst[1][0].c[0][0] = 1;
	cst[1][0].c[1][1] = 0;
	cst[1][0].c[1][0] = inf;
	
	cst[1][1].c[0][0] = cst[1][1].c[1][1] = 1;
	cst[1][1].c[0][1] = cst[1][1].c[1][0] = 1;
	
	cin >> n;
	cnr[0] = cnl[0] = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		cnr[a[i]]++;
		s += a[i];
	}
	bld(1, 0, n + 1);
	for(int i = 1; i <= n; i++){
		cost cs = get(1, 0, n + 1, 0, a[i]);
		cnr[a[i]]--;
		cnl[a[i]]++;
		upd(1, 0, n + 1, a[i], a[i] + 1);
		dp[i] = min({cs.c[0][0], cs.c[0][1], cs.c[1][0], cs.c[1][1]});
		ans += dp[i];
	}
	
	cout << ans << "\n";
	
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
 
const int N = 200200;
int n;
char s[N];
int bal[N];
int pos[N];
 
void solve() {
	scanf("%d %s", &n, s);
	int b = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '0')
			b++;
		else
			b--;
	}
	if (b < 0) {
		for (int i = 0; i < n; i++)
			s[i] ^= 1;
		reverse(s, s + n);
		b *= -1;
	}
	bal[0] = (n + b) / 2;
	for (int i = 0; i < n; i++)
		bal[i + 1] = bal[i] + (s[i] == '0' ? -1 : 1);
	assert(bal[n] == (n - b) / 2);
	for (int i = 0; i <= n; i++)
		pos[i] = -1;
	for (int i = 0; i <= n; i++)
		pos[bal[i]] = i;
	int ans = 0;
	int l = 0;
	while(l < (n + b) / 2) {
		if (bal[l + 1] < bal[l]) {
			l++;
			continue;
		}
		if (bal[l] <= (n - b) / 2) {
			ans++;
			break;
		}
		int r = pos[bal[l]];
		assert(r > l);
		ans++;
		for (int i = l + 1; i < r; i++) {
			if (2 * i > l + r) {
				bal[i] = bal[l] - (r - i);
			} else {
				bal[i] = bal[l] - (i - l);
			}
			pos[bal[i]] = max(pos[bal[i]], i);
		}
	}
	printf("%d\n", ans);
}
 
int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int t;
	scanf("%d", &t);
	while(t--) solve();
 
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        if(n == 1 && m == 1){
            cout << "0\n";
        }
        else if(min(n, m) == 1){
            cout << "1\n";
        }
        else cout << "2\n";
    }
}

For an integer $$$x$$$ we can determine whether or not it's possible to make the array palindrome by removing some of the elements equal to $$$x$$$.

We claim that it is possible iff removing all appearances of $$$x$$$ makes the array palindrome.

Imagine we made the array palindrome by removing some of the elements equal to $$$x$$$. It's obvious that after removing the rest of the elements equal to $$$x$$$ the array remains palindrome.

$$$\textbf{Read the Hints and Assumptions before reading this.}$$$

//khodaya khodet komak kon
# include <bits/stdc++.h>
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 2e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;
 
int qq, n, m, a[xn], b[xn];
bool ans;
 
void check(int x){
	m = 0;
	for (int i = 1; i <= n; ++ i)
		if (a[i] != x)
			b[++ m] = a[i];
	for (int i = 1; i <= m; ++ i)
		if (b[i] != b[m + 1 - i])
			return;
	ans = true;
}
 
int main(){
	fast_io;
 
	cin >> qq;
	while (qq --){
		cin >> n, ans = true;
		for (int i = 1; i <= n; ++ i)
			cin >> a[i];
		for (int i = 1; i <= n; ++ i){
			if (a[i] != a[n + 1 - i]){
				ans = false;
				check(a[i]);
				check(a[n + 1 - i]);
				break;
			}
		}
		if (ans)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
 
	return 0;
}

$$$\textbf{Read the Hints and Assumptions before reading this.}$$$

//In the name of God
#include <bits/stdc++.h>
using namespace std;
 
typedef int ll;
typedef pair<ll, ll> pll;
 
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
 
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
 
ll q, n, a[maxn], b[maxn];
 
bool ok(ll x){
	ll c = 0;
	for(ll i = 0; i < n; i++){
		if(x - 1 - a[i] <= c && c <= b[i]) c++;
	}
	return c >= x;
}
 
int main(){
    fast_io;
    
    cin >> q;
    while(q--){
        cin >> n;
        for(ll i = 0; i < n; i++){
        	cin >> a[i] >> b[i];
    	}
    	ll l = -1, r = n + 1, mid;
    	while(r - l > 1){
    		mid = (l + r) >> 1;
    		if(ok(mid)) l = mid;
    		else r = mid;
    	}
    	cout << l << "\n";
    }
    return 0;
}

//In The Name of God
//I usually forget about the previous line...

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

using namespace std;

typedef long long ll;

const int maxBt = 30;
const int mod = 1e9+7;

int cnt[maxBt];

int slv(){
    int n;
    cin >> n;

    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    int to[n+1]; //powers of 2

    to[0] = 1;
    for(int i = 1; i <= n; i++){
        to[i] = to[i-1]*2 % mod;
    }

    for(int i = 0; i < n; i++){
        int x = 0;
        for(int k = 0; k < maxBt; k++){
            if(a[i] & 1)break;
            a[i] >>= 1;
            x++;
        }
        cnt[x]++;
    }

    int ans = to[n] - to[n-cnt[0]] + mod;
    if(ans >= mod)ans -= mod;

    int y = n-cnt[0];

    for(int l = 1; l < maxBt; l++){
        int x = y;
        y -= cnt[l];
        if(x-y < 2)continue;
        int delta = to[x-1]-to[y]+mod;
        if(delta >= mod)delta -= mod;
        ans += delta;
        if(ans >= mod)ans -= mod;
    }

    return ans;
}


signed main(){
    IOS

    cout << slv() << '\n';

}

$$$\textbf{Read the Hints and Assumptions before reading this.}$$$

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

const int xn = 2e5 + 10;

int qq, n, a[xn], ans, res, ptr;
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

	cin >> qq;
	while (qq --){
		cin >> n, ans = 0;
		for (int i = 1; i <= n; ++ i)
			cin >> a[i];
		for (int i = 1; i <= n; ++ i){
			if (a[i] == a[i - 1])
				continue;
			res = 0, ptr = i;
			while (ptr <= n)
				ptr = lower_bound(a + ptr + 1, a + n + 1, 2 * a[ptr] - a[i]) - a, ++ res;
			ans = max(ans, res);
		}
		cout << n - ans << "\n";
	}

	return 0;
}

Let's call $$$c_v$$$ as the sum of weights of all edges connected to vertex $$$v$$$.

It's obvious that when $$$c_v$$$ is even, $$$v$$$ would never be Oddysey.

Here we propose an algorithm to make all vertices with odd $$$c_v$$$ Oddysey.

$$$\textbf{Read the Hints and Assumptions before reading this.}$$$

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=100000000000000100LL;
const int mod=1000000007;
const int MAXN=300010, LOG=19;
 
int n, m, mm, k, u, v, x, y, t, a, b;
int U[MAXN], V[MAXN], W[MAXN], ans[MAXN];
int deg[MAXN], parr[MAXN][3], mark[MAXN];
vector<int> G[MAXN][3], E[MAXN];
vector<pii> G2[MAXN];
 
inline void orient(int i, int u){
	if (u==U[i]){
		ans[i]=1;
		deg[U[i]]-=W[i];
		deg[V[i]]+=W[i];
	}
	else{
		ans[i]=2;
		deg[U[i]]+=W[i];
		deg[V[i]]-=W[i];
	}
}
 
void MergePath(int i, int w){
	mm++;
	int v=i;
	while (1){
		while (SZ(G[v][w]) && mark[G[v][w].back()]) G[v][w].pop_back();
		if (G[v][w].empty()) break ;
		int i=G[v][w].back();
		assert(!mark[i]);
		mark[i]=1;
		E[mm].pb(i);
		int u=(U[i]^V[i]^v);
		parr[u][w]^=1;
		parr[v][w]^=1;
		v=u;
	}
	if (E[mm].empty()){
		mm--;
		return ;
	}
	G2[i].pb({v, mm});
	G2[v].pb({i, -mm});
}
void dfs(int v){
	while (SZ(G2[v]) && mark[abs(G2[v].back().second)]) G2[v].pop_back();
	if (G2[v].empty()) return ;
	int u=G2[v].back().first, id=G2[v].back().second;
	if (id<0){
		id*=-1;
		reverse(all(E[id]));
	}
	mark[id]=1;
	for (int i:E[id]){
		orient(i, v);
		v^=V[i]^U[i];
	}
	assert(v==u);
	dfs(u);
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=0; i<m; i++){
		cin>>U[i]>>V[i]>>W[i];
		parr[U[i]][W[i]]^=1;
		parr[V[i]][W[i]]^=1;
		G[U[i]][W[i]].pb(i);
		G[V[i]][W[i]].pb(i);
	}
	int sum=0;
	for (int i=1; i<=n; i++) sum+=parr[i][1];
	for (int i=1; i<=n; i++) for (int w:{1, 2}) if (parr[i][w]) MergePath(i, w);
	for (int i=1; i<=n; i++) for (int w:{1, 2}) MergePath(i, w);
 
	for (int i=0; i<m; i++){
		assert(mark[i]);
		mark[i]=0;
	}
	for (int i=1; i<=n; i++) if (SZ(G2[i])&1) dfs(i);
	for (int i=1; i<=n; i++) dfs(i);
 
	cout<<sum<<"\n";
	for (int i=0; i<m; i++) cout<<ans[i]; cout<<"\n";
 
	return 0;
}

$$$\textbf{Read the Hints and Assumptions before reading this.}$$$

//In the name of God
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
const ll maxn = 3e5 + 100;
const ll lg = 20;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
 
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
 
ll n, par[maxn][lg], h[maxn][lg], ls[maxn + maxn], ps[maxn], nxt[maxn], a[maxn], d[maxn], p[maxn];
string s;
 
ll check(ll v, ll u){
	for(ll i = lg; i--;){
		if(d[v] < (1 << i) || d[u] < (1 << i)) continue;
		if(h[v][i] == h[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	if(d[v] == 0) return 1;
	return (h[v][0] < h[u][0]);
}
 
int main(){
	fast_io;
	p[0] = 1;
	for(ll i = 1; i < maxn; i++){
		p[i] = p[i - 1] * 2 % mod;
	}
    
	cin >> s;
	n = Sz(s);
	s = ' ' + s;
	for(ll i = 1; i <= n; i++){
		ps[i] = ps[i - 1] + (s[i] == '(' ? 1 : -1);
	}
	for(ll i = n + 1; i > 0; i--){
		nxt[i] = i;
		if(s[i] == '(' && ls[ps[i - 1] + maxn]){
			nxt[i] = ls[ps[i - 1] + maxn];
		}
		ls[ps[i - 1] + maxn] = i;
	}
	a[n + 1] = n + 1;
	for(ll i = n; i > 0; i--){
		par[i][0] = a[i + 1];
		h[i][0] = (s[i] == '(' ? 0 : 1);
		d[i] = d[par[i][0]] + 1;
		for(ll j = 1; j < lg; j++){
			if(d[i] < (1 << j)) break;
			par[i][j] = par[par[i][j - 1]][j - 1];
			h[i][j] = (h[i][j - 1] * p[(1 << (j - 1))] + h[par[i][j - 1]][j - 1]) % mod;
		}
		a[i] = i;
		if(check(a[nxt[i]], i)){
			a[i] = a[nxt[i]];
		}
	}
	ll v = a[1];
	while(v != n + 1){
		cout << (h[v][0] ? ')' : '(');
		v = par[v][0];
	}
	cout << "\n";
 
    return 0;
}

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=100000000000000100LL;
const int mod=1000000007;
const int MAXN=300010, LOG=19;
 
int n, m, k, u, v, x, y, t, a, b, ans;
int par[LOG][MAXN], h[MAXN], P[MAXN];
int stt[MAXN], fnt[MAXN], timer=1;
int fen[MAXN];
vector<int> G[MAXN], vec[MAXN], out;
 
int GetPar(int v, int k){
	for (int i=0; k; i++) if (k&(1<<i)){
		k^=(1<<i);
		v=par[i][v];
	}
	return v;
}
inline void add(int pos, int val){
	for (; pos<MAXN; pos+=pos&-pos) fen[pos]+=val;
}
inline int get(int pos){
	int res=0;
	for (; pos; pos-=pos&-pos) res+=fen[pos];
	return res;
}
inline int get2(int v){ return get(fnt[v]-1)-get(stt[v]-1);}
void dfs(int node){
	stt[node]=timer++;
	for (int v:G[node]) dfs(v);
	fnt[node]=timer;
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=2; i<=n; i++){
		cin>>par[0][i];
		G[par[0][i]].pb(i);
		h[i]=h[par[0][i]]+1;
		for (int j=1; j<LOG; j++)
			par[j][i]=par[j-1][par[j-1][i]];
	}
	dfs(1);
	while (m--){
		cin>>x>>y;
		if (h[x]>h[y]) swap(x, y);
		if (par[0][y]==x) kill(-1)
		vec[x].pb(y);
	}
	iota(P+1, P+n+1, 1);
	sort(P+1, P+n+1, [](int i, int j){ return h[i]>h[j];});
	vector<pii> crossE;
	for (int i=1; i<=n; i++){
		int x=P[i];
		for (int y:vec[x]){
			if (h[x]==h[y]){
				crossE.pb({x, y});
				continue ;
			}
			int yy=GetPar(y, h[y]-h[x]-1);
			if (par[0][yy]!=x){
				crossE.pb({x, y});
				continue ;
			}
			if (get2(yy)-get2(y)) continue ;
			ans++;
			out.pb(yy);
			add(stt[yy], +1);
		}
	}
	for (pii p:crossE){
		int x=p.first, y=p.second;
		if (get2(x)+get2(y)<ans) continue ;
		out.pb(1);
		ans++;
		break ;
	}
	cout<<ans<<"\n";
 
	return 0;
}

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=100000000000000100LL;
const int mod=1000000007;
const int MAXN=300010, LOG=20;
 
int n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN], dp[MAXN], dead[MAXN];
vector<int> G[MAXN];
 
void dfs(int node){
	for (int v:G[node]) if (v!=par[node]){
		par[v]=node;
		dfs(v);
		dp[node]^=dp[v]+1;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<n; i++){
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	ans=dp[1];
	cout<<1+(ans==0);
	dead[1]=1;
	for (int i=2; i<=n; i++){
		vector<int> vec;
		int v=i;
		while (!dead[v]){
			vec.pb(v);
			dead[v]=1;
			v=par[v];
		}
		reverse(all(vec));
		for (int v:vec){
			// Kill v
			ans^=dp[v]+1;
			ans^=dp[v];
			ans^=1;
		}
		cout<<1+(ans==0);
	}
	cout<<"\n";
 
	return 0;
}