#include <iostream>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef int ll;
inline char gc(){
	static char buf[1<<14],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(ll &x){
	x=0;bool f=1;char c=gc();
	for(;!isdigit(c);c=gc()){if(c=='-')f^=1;if(c==-1)return-1;}
	for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);x=f?x:-x;
	return 1;
}
#define pc putchar
inline void wr(ll x){
	if(x<0)pc('-'),x=-x;
	if(x>9)wr(x/10);pc(x%10|48);
}
const ll N=1e5+10;
ll n,fa[N];
map<ll,ll>vis[N];
queue<pair<ll,ll> >Q;
set<ll>s[N];
inline ll fid(ll x){return fa[x]==x?x:fa[x]=fid(fa[x]);}
int main(){
	read(n);
	for (ll i=1,x,y;i<=2*n-2;++i){
		read(x),read(y);
		++vis[x][y],++vis[y][x];
		if (vis[x][y]==2) Q.push(make_pair(x,y));
		s[x].insert(y);
		s[y].insert(x);
	}
	for (ll i=1;i<=n;++i) fa[i]=i;
	while (!Q.empty()){
		pair<ll,ll>A=Q.front();Q.pop();
		ll x=fid(A.first),y=fid(A.second);
		if (x==y) continue;
		s[x].erase(y),s[y].erase(x);
		if (s[x].size()>s[y].size()) swap(x,y);
		for (set<ll>::iterator it=s[x].begin();it!=s[x].end();++it){
			ll i=*it;
			s[i].erase(x);
			s[i].insert(y),s[y].insert(i);
			++vis[y][i],++vis[i][y];
			if (vis[y][i]==2) Q.push(make_pair(y,i));
		}
		s[x].clear();
		fa[x]=y;
	}
	for (ll i=1;i<=n;++i) if (fid(i)!=fid(1)) return puts("NO"),0;
	puts("YES");
	return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 <iostream>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef int ll;
inline char gc(){
	static char buf[1<<14],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(ll &x){
	x=0;bool f=1;char c=gc();
	for(;!isdigit(c);c=gc()){if(c=='-')f^=1;if(c==-1)return-1;}
	for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);x=f?x:-x;
	return 1;
}
#define pc putchar
inline void wr(ll x){
	if(x<0)pc('-'),x=-x;
	if(x>9)wr(x/10);pc(x%10|48);
}
const ll N=1e5+10;
ll n,fa[N];
map<ll,ll>vis[N];
queue<pair<ll,ll> >Q;
set<ll>s[N];
inline ll fid(ll x){return fa[x]==x?x:fa[x]=fid(fa[x]);}
int main(){
	read(n);
	for (ll i=1,x,y;i<=2*n-2;++i){
		read(x),read(y);
		++vis[x][y],++vis[y][x];
		if (vis[x][y]==2) Q.push(make_pair(x,y));
		s[x].insert(y);
		s[y].insert(x);
	}
	for (ll i=1;i<=n;++i) fa[i]=i;
	while (!Q.empty()){
		pair<ll,ll>A=Q.front();Q.pop();
		ll x=fid(A.first),y=fid(A.second);
		if (x==y) continue;
		s[x].erase(y),s[y].erase(x);
		if (s[x].size()>s[y].size()) swap(x,y);
		for (set<ll>::iterator it=s[x].begin();it!=s[x].end();++it){
			ll i=*it;
			s[i].erase(x);
			s[i].insert(y),s[y].insert(i);
			++vis[y][i],++vis[i][y];
			if (vis[y][i]==2) Q.push(make_pair(y,i));
		}
		s[x].clear();
		fa[x]=y;
	}
	for (ll i=1;i<=n;++i) if (fid(i)!=fid(1)) return puts("NO"),0;
	puts("YES");
	return 0;
}
```