409055: GYM103428 A Goodbye, Ziyin!

My Dearest Allie:

I couldn't sleep last night because I know that it's over between us. I'm not bitter anymore, because I know that what we had was real.

And if in some distant place in the future we see each other in our new lives, I'll smile at you with joy and remember how we spent a summer beneath the trees, learning from each other and growing in love. The best love is the kind that awakens the soul and makes us reach for more, that plants a fire in our hearts and brings peace to our minds. And that's what you've given me. That's what I'd hoped to give to you forever.

I love you. I'll be seeing you.

Through time passes, there is always someone we will never forget.

"Although there were millions of trees in the world, there was only one that The Little Prince took care of with his heart. And although there are countless people in the world, there is only one that I take care of with my heart." said Zayin to Ziyin with affection.

"Millions of trees? I may not agree with you. Just a tree could have millions of structure." answered Ziyin proudly, "Let's do the some math."

...

Thinking of the days they have happily spent together, Zayin can't help bursting into tears. Though Ziyin has been gone for a long time, Zayin still misses her every much.

He remembers it was a sunny afternoon when Ziyin and him were lying in the yard, resting beneath the shade of a tree, working on the number of nodes satisfying that if the tree is rooted by the node, the rooted tree is a rooted binary tree.

When times smoothes all sorrows, Zayin also forgets the answer of the problem. He only remember the structure of the tree. Maybe it's time for Zayin to let all memories about Ziyin go, but he still want to figure out the answer out of sentiment.

As Zayin's friend, you may want Zayin to get released as soon as possible, can you help him?

In short, given an unrooted tree, please calaculate how many nodes satisfying that if the tree is rooted by the node, the rooted tree is a rooted binary tree.

The first line of the input contains an integer $$$n\ (1\le n\le 10^6)$$$, indicating the number of nodes.

Each of the next $$$n-1$$$ line contains two integers $$$u\ (1\le u\le n)$$$ and $$$v\ (1\le u\le n)$$$, denoting that there is a edge connecting node $$$u$$$ and $$$v$$$.

It's guatanteed that the $$$n-1$$$ edges form a tree.

Print an integer, denoting the number of satisfactory nodes.

6
1 2
1 3
2 4
2 5
3 6

5

A rooted binary tree is a rooted tree in which every nodes have at most 2 childrens.