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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
typedef pair<int,bool> P;

const int MAX_N=1e5;

set<P> G[MAX_N];

typedef pair<int,int> edge;

int main(){
	stack<edge> st;
	int N;
	scanf("%d",&N);
	REP(i,N-1){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;
		b--;
		G[a].insert(P(b,false));
		G[b].insert(P(a,false));
	}
	REP(i,N-1){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;
		b--;
		G[a].insert(P(b,true));
		G[b].insert(P(a,true));
		st.push(edge(a,b));
	}
	int c=0;
	while(!st.empty()){
		edge e=st.top();
		st.pop();
		int from=e.first,to=e.second;
		auto ite=G[from].find(P(to,false));
		if (ite!=G[from].end()){
			auto ite2=ite;
			ite2++;
			if (ite2!=G[from].end() && ite2->first==to){
				if (G[from].size()<G[to].size()){
					swap(from,to);
				}
				c++;
				G[from].erase(P(to,false));
				G[from].erase(P(to,true));
				G[to].erase(P(from,false));
				G[to].erase(P(from,true));
				for(auto ite3=G[to].begin();ite3!=G[to].end();){
					st.push(edge(from,ite3->first));
					G[ite3->first].erase(P(to,ite3->second));
					G[ite3->first].insert(P(from,ite3->second));
					G[from].insert(*ite3);
					ite3=G[to].erase(ite3);
				}
			}
		}
	}
	if (c==N-1){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}