Problem: Dasha decided to have a rest after solving the problem. She had been ready to start her favourite activity — origami, but remembered the puzzle that she could not solve. 

<image>

The tree is a non-oriented connected graph without cycles. In particular, there always are n - 1 edges in a tree with n vertices.

The puzzle is to position the vertices at the points of the Cartesian plane with integral coordinates, so that the segments between the vertices connected by edges are parallel to the coordinate axes. Also, the intersection of segments is allowed only at their ends. Distinct vertices should be placed at different points. 

Help Dasha to find any suitable way to position the tree vertices on the plane.

It is guaranteed that if it is possible to position the tree vertices on the plane without violating the condition which is given above, then you can do it by using points with integral coordinates which don't exceed 1018 in absolute value.

Input

The first line contains single integer n (1 ≤ n ≤ 30) — the number of vertices in the tree. 

Each of next n - 1 lines contains two integers ui, vi (1 ≤ ui, vi ≤ n) that mean that the i-th edge of the tree connects vertices ui and vi.

It is guaranteed that the described graph is a tree.

Output

If the puzzle doesn't have a solution then in the only line print "NO".

Otherwise, the first line should contain "YES". The next n lines should contain the pair of integers xi, yi (|xi|, |yi| ≤ 1018) — the coordinates of the point which corresponds to the i-th vertex of the tree.

If there are several solutions, print any of them. 

Examples

Input

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

Output

YES
0 0
1 0
0 1
2 0
1 -1
-1 1
0 2

Input

6
1 2
2 3
2 4
2 5
2 6


Output

NO


Input

4
1 2
2 3
3 4

Output

YES
3 3
4 3
5 3
6 3

Note

In the first sample one of the possible positions of tree is: <image>

Solution (in JAVA):

Solution:
             import java.util.*; 
                    import java.math.*;
                    import java.io.*;
                    import java.text.DecimalFormat;
                    import java.math.BigInteger;
                    public class Main{
                        //static int d=20;
                        static long mod=1000000007 ;
                        static HashMap<String,Double> hm=new HashMap<>(); 
                        static ArrayList<ArrayList<Integer>> arr;
                        static long[] dp1,dp2;
                        static int[] a;
                        static int[] vis,num;
                        static long max;
                        static HashSet<String> hs;
                        static int id;
                        public static void main(String[] args)  throws IOException {
                            boolean online =false;
                            String fileName = "C-large-practice";
                            PrintWriter out; 
                            if (online) {
                                s.init(new FileInputStream(new File(fileName + ".in")));
                                 out= new PrintWriter(new FileWriter(fileName + "out.txt"));
                            }
                             else {
                                s.init(System.in);   
                            
                                out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
                            }//r,b,y,g
                           
                            int n=s.ni();
                            arr=new ArrayList<>();
                            for(int i=0;i<n;i++)
                                arr.add(new ArrayList<Integer>());
                            for(int i=0;i<n-1;i++){
                                int x=s.ni()-1;
                                int y=s.ni()-1;
                                arr.get(x).add(y);
                                arr.get(y).add(x);

                            }
                            int flag=0;
                            for(int i=0;i<n;i++){
                                if(arr.get(i).size()>4){
                                    out.println("NO");
                                    flag=1;
                                    break;
                                }
                            }
                            if(flag==0){
                                long[][] ans=new long[n][2];
                                ans[0][1]=0;
                                ans[0][0]=0;
                                int[] vis=new int[n];
                                hs=new HashSet<>();
                                dfs2(0,0,0,0,vis,ans,(long)1e10);
                                out.println("YES");
                                for(long[] x:ans){
                                    out.println(x[0]+" "+x[1]);
                                }

                            }
                            out.close();
             
                        }
                        static class query implements Comparable<query> {
                            long x,y;
                            int id;
                            public query(int u,long a,long b){
                                {   id=u;
                                    x=a;
                                    y=b;
                                }
                                
                                
                                
                            }
                            public int compareTo(query o){
                                return (int)Math.signum( o.x-x);
                            }
                            
                        }
                        public static void dfs2(int num,int c,long x,long y,int[] vis,long[][] ans,long add){
                            vis[c]=1;
                            ans[c][0]=x;
                            ans[c][1]=y;
                            int id=0;
                            hs.add(x+" "+y);
                            ArrayList<Integer> arr2=arr.get(c);
                            for(int i=0;i<arr2.size();i++){
                                int z=arr2.get(i);
                                if(vis[z]==1)
                                    continue;
                                if(num!=1 && !hs.contains((x-add)+" "+y)){
                                    dfs2(2,z,x-add,y,vis,ans,add/2);
                                }
                                else if(num!=2 && (!hs.contains((x+add)+" "+y)))
                                    dfs2(1,z,x+add,y,vis,ans,add/2);
                                else if(num!=3 && !hs.contains((x)+" "+(y+add)))
                                    dfs2(4,z,x,y+add,vis,ans,add/2);
                                else
                                    dfs2(3,z,x,y-add,vis,ans,add/2);
                                
                            }
                            //st.push(x);

                        }
                        
                        public static void dfs(int x,int[] vis,Stack<Integer> st){
                            vis[x]=1;
                            ArrayList<Integer> arr2=arr.get(x);
                            Collections.sort(arr2);
                            for(int i=arr2.size()-1;i>=0;i--){
                                int z=arr2.get(i);
                                if(vis[z]==0)
                                    dfs(z,vis,st);
                            }
                            st.push(x);

                        }
                        public static long gcd(long a, long b){
                                if (a == 0) return b;
                                return gcd(b % a, a);
                        }
                            
                        public static boolean check(long x){
                            if(x%4==0 || x%7==0 || x%11==0)
                                return true;
                            if(x<4 || x<7 || x<11)
                                return false;
                            if(x%2==0){
                                return check(x/2);
                            }
                            else
                                return check(x/2) && check((x+1)/2);
                        }
                        public static int angle(int x1,int x2,int x3,int y1,int y2,int y3){
                            long val=(y2-y1)*1L*(x3-x2)-(y3-y2)*1L*(x2-x1);
                            if(val<0)
                                return 1;
                            else if(val>0)
                                return -1;
                            else
                                return 0;
                        }
                        
                        static class BIT{
                        
                            int N;
                            long tree[];
                            
                            BIT(int N){
                                this.N = N;
                                tree = new long[N + 1];
                            }
                            
                            void update(int idx,long val){
                                while(idx <= N){
                                    tree[idx]+=val;
                                    idx += (idx & -idx);
                                }
                            }
                            
                            long query(int l,int r){
                                if(l == 1)
                                    return read(r);
                                else
                                    return read(r) - read(l-1);
                            }
                            
                            long read(int idx){
                                long sum = 0;
                                while(idx > 0){
                                    sum += tree[idx];
                                    idx -= (idx & -idx);
                                }
                                return sum;
                            }
                        }
                        public static boolean pal(String a){
                            int i=0;
                            int j=a.length()-1;
                            while(i<j){
                                if(a.charAt(i)!=a.charAt(j)){
                                    return false;
                                }
                                i++;
                                j--;
                            }
                            return true;
                                
                        }
                        public static long find(long n,long k){
                            if(n==2){
                                if(k==1 || k==3)
                                    return 1;
                                else
                                    return 2;
                            }
                            long t=pow2(2,n,mod)-1;
                            long z=(t+1)/2;
                            if(k==z)
                                return n;
                            if(k<z)
                                return find(n-1,k);
                            else
                                return find(n-1,k-z);
                        }
                        public static long pow2(long a,long b,long mod){
                                long ans=1;
                                while(b>0){
                                    if(b%2==1)
                                        ans=(a*ans)%mod;
                                    a=(a*a)%mod;
                                    b/=2;
                                }
                                return  ans;
                        }
                        public static long pow3(long a,long b){
                                long ans=1;
                                while(b>0){
                                    if(b%2==1)
                                        ans=(a*ans);
                                    a=(a*a);
                                    b/=2;
                                }
                                return  ans;
                        }
             
                         static class name implements Comparable<name> {
                            long l,b,h;
                            public name(long   x,long y,long z){
                                {
                                    l=x;
                                    b=y;
                                }
                                
                                
                                h=z;
                            }
                            public int compareTo(name o){
                                return -(int)(l*b-o.l*o.b);
                            }
                            
                        }
                        public static class s {
                            static BufferedReader reader;
                            static StringTokenizer tokenizer;
                        
                            /** call this method to initialize reader for InputStream */
                            static void init(InputStream input) {
                                reader = new BufferedReader(
                                            new InputStreamReader(input) );
                                tokenizer = new StringTokenizer("");
                            }   
                        
                            /** get next word */
                            static String ns() throws IOException {
                                while ( ! tokenizer.hasMoreTokens() ) {
                                    //TODO add check for eof if necessary
                                    tokenizer = new StringTokenizer(
                                        reader.readLine() );
                                }
                                return tokenizer.nextToken();
                            }
                        
                            static int ni() throws IOException {
                                return Integer.parseInt( ns() );
                            }
                        
                            static double nd() throws IOException {
                                return Double.parseDouble( ns() );
                            }
                            static long nl() throws IOException {
                                return Long.parseLong( ns() );
                            }
                        }
                    }