[USACO10NOV] Chocolate Milk S

### 题目描述 农民约翰的牛奶生产和运输是一个复杂的过程，他用挤奶器给他的那么多头奶牛挤奶，然后流入管道。 每一个管道把一台挤奶器和一个可能连有一台或多台挤奶器的接口连接起来（这样几个管道里的牛奶就汇合了）。然后牛奶流入附加管道（连在各个接口之间的管道）直到流到中央管道，通向储存室。 然后这些牛奶又经历一个逆向的过程通过管道分流到各个牛奶桶，最后被运至市场。 约翰发现对于牛奶来说，最多只有一种方式从一个接口流到另一个接口。并且由于约翰是一个高效率的人，他需要确保每一个管道都有牛奶经过，也就是说，没有多余的管道。 如果我们把每个挤奶机、接口和奶罐都看成一个节点，就共有 $N$ 个节点，输入有序的节点对 $A_{i}$ 和 $B_{i}$ ，代表牛奶从 $A_{i}$ 节点流到 $B_{i}$ 节点，如果没有相对应的父节点，那就说明这是一个挤奶器，同样的如果没有对应的尾节点，则这是一个奶罐。 这几个月巧克力牛奶的需求量激增，所以约翰想要在某一个接口处安装一个巧克力混合器以得到巧克力牛奶，为了节约，约翰只买了一个巧克力混合器。所以他想把这个东西放到一个所有牛奶都能经过的接口，事实上，有这种接口存在。 帮助约翰找到这样的节点（注意：不能把巧克力混合器放在挤奶机里）。 ``` 1 ----+ | v 2 --> 4 --> 6 ------------------> 7 --> 8 ^ | | | 3 --> 5 ----+ + --> 9 ``` 所有的牛奶都会流经6号或7号节点，所以巧克力混合器可以放在这两个节点上。 ### 输入格式 第 $1$ 行一个整数 $N$。 第 $2$ 到第 $N$ 行：包含空格分隔的两个整数，描述第 $i$ 个管道连接的两个节点：$A_{i}$ 和 $B_{i}$。 ### 输出格式 第 $1$ 行到 ？？行：每行一个整数，升序输出每个可以安装巧克力混合器的节点。

Farmer John's milk production and shipping system is an intricate one! He uses milking machines for his many cows to harvest the milk that then flows into pipes. Each of these pipes connects a milking machine to a joint, where it might be joined by exactly one more pipe (the milk flowing through both pipes merges). The milk then flows through additional pipes (which all start and end at joints) until it reaches the long central pipe connecting to the distribution room. The milk then goes through a reverse process of splitting at various joints until it is flows into milk tanks that are picked up and taken to market. Farmer John notices that there is at most one way for milk to travel from one joint to any other joint. Furthermore, since Farmer John is an efficient man by nature, he has made sure that milk will flow through each and every pipe; in other words, no pipe is unneeded. If we think of a milking machine, joint, or milk tank as a node, there are N (2 <= N <= 100,000) nodes in total (and N-1 pipes connecting them). The input describes each pipe as an ordered pair of nodes, A\_i (1 <= A\_i <= N) and B\_i (1 <= B\_i <= N; A\_i < B\_i) indicating milk flows from node A\_i to node B\_i. If there is no pipe coming in to A\_i, it is a milking machine. Likewise, if no pipe goes out from B\_i, it is a tank. The demand of chocolate milk has skyrocketed in recent months, and Farmer John wants to install a chocolate inserter at one of the joints so he can create delicious chocolate milk for customers. Being thrifty, Farmer John has only bought one chocolate inserter, so he wants to place it at a joint through which all the milk passes. He knows that such a joint exists. Help Farmer John find all the possible places he can install the chocolate inserter. (Note that Farmer John cannot install the chocolate inserter at the same location as a milking machine.) As an example, consider a milking setup like this one: ```cpp 1 ----+ | v 2 --> 4 --> 6 ------------------> 7 --> 8 ^ | | | 3 --> 5 ----+ + --> 9 ``` Visual inspection shows that the chocolate inserter can be installed at either joint 6 or 7, as all milk flows through those joints.

\* Line 1: A single integer: N \* Lines 2..N: Line i+1 contains two space-separated integers that describe a pipe's connectivity: A\_i and B\_i

\* Lines 1..??: Integers, one per line and in ascending order, each denoting a possible joint at which to install the chocolate inserter.

9 
1 4 
3 5 
2 4 
5 6 
6 7 
7 8 
4 6 
7 9 

6 
7