#include <bits/stdc++.h>

using namespace std ;

const int sz = 1e5 + 7 ;

set<int> st[sz] ;
set< pair<int,int> > container ;
set<int>::iterator it ;
set<int>::iterator it2 ;
vector< pair<int,int> > qu ;
int par[sz] , qu_siz ;

int find_par(int u)
{
	if(u == par[u]) return u ;

	return par[u] = find_par(par[u]);
}

void add(int u,int v)
{
	it = st[u].find(v) ;

	if(it == st[u].end()) st[u].insert(v) ;

	else
	{
		st[u].erase(v);

		if(v<u)
			swap(u,v);

		if(container.find(make_pair(u,v)) == container.end())
		{
			container.insert(make_pair(u,v));
			qu.push_back(make_pair(u,v));
			qu_siz++;
		}
	}
}

int main()
{
	int n , u , v , edge ;

	scanf("%d",&n);

	edge = n-1 ;
	edge = edge*2 ;

	for(int i=0 ; i<edge ; i++)
	{
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}

	pair<int,int> temp ;

	for(int i=1 ; i<=n ; i++) 
		par[i] = i ;

	for(int i=0 ; i<qu_siz ; i++)
	{
		temp = qu[i] ;

		u = temp.first ;
		v = temp.second ;

		u = find_par(u);
		v = find_par(v);

		if(u == v)
			continue ;

		if(st[u].size()>st[v].size()) swap(u,v);

		par[u] = v ;

		for(it2 = st[u].begin() ; it2 != st[u].end() ; it2++)
		{
			st[*it2].erase(u);
			add(*it2,v);
			add(v,*it2);
		}

		st[u].clear();
	}

	if(qu_siz + 1 == n) puts("YES");

	else puts("NO");

	return 0 ;
}
### Prompt

In CPP, your task is to solve the following problem:

There is a tree with N vertices numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation N-1 times:

* Select a simple path that consists of only blue edges, and remove one of those edges.
* Then, span a new red edge between the two endpoints of the selected path.



His objective is to obtain a tree that has a red edge connecting vertices c_i and d_i, for each i.

Determine whether this is achievable.

Constraints

* 2 ≤ N ≤ 10^5
* 1 ≤ a_i,b_i,c_i,d_i ≤ N
* a_i ≠ b_i
* c_i ≠ d_i
* Both input graphs are trees.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

Print `YES` if the objective is achievable; print `NO` otherwise.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

YES


Input

5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5


Output

YES


Input

6
1 2
3 5
4 6
1 6
5 1
5 3
1 4
2 6
4 3
5 6


Output

NO

### Response

```cpp
#include <bits/stdc++.h>

using namespace std ;

const int sz = 1e5 + 7 ;

set<int> st[sz] ;
set< pair<int,int> > container ;
set<int>::iterator it ;
set<int>::iterator it2 ;
vector< pair<int,int> > qu ;
int par[sz] , qu_siz ;

int find_par(int u)
{
	if(u == par[u]) return u ;

	return par[u] = find_par(par[u]);
}

void add(int u,int v)
{
	it = st[u].find(v) ;

	if(it == st[u].end()) st[u].insert(v) ;

	else
	{
		st[u].erase(v);

		if(v<u)
			swap(u,v);

		if(container.find(make_pair(u,v)) == container.end())
		{
			container.insert(make_pair(u,v));
			qu.push_back(make_pair(u,v));
			qu_siz++;
		}
	}
}

int main()
{
	int n , u , v , edge ;

	scanf("%d",&n);

	edge = n-1 ;
	edge = edge*2 ;

	for(int i=0 ; i<edge ; i++)
	{
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}

	pair<int,int> temp ;

	for(int i=1 ; i<=n ; i++) 
		par[i] = i ;

	for(int i=0 ; i<qu_siz ; i++)
	{
		temp = qu[i] ;

		u = temp.first ;
		v = temp.second ;

		u = find_par(u);
		v = find_par(v);

		if(u == v)
			continue ;

		if(st[u].size()>st[v].size()) swap(u,v);

		par[u] = v ;

		for(it2 = st[u].begin() ; it2 != st[u].end() ; it2++)
		{
			st[*it2].erase(u);
			add(*it2,v);
			add(v,*it2);
		}

		st[u].clear();
	}

	if(qu_siz + 1 == n) puts("YES");

	else puts("NO");

	return 0 ;
}
```