USACO 2019 US Open Contest, Bronze Problem 2 Milk Factory

Category: 國(guó)際競(jìng)賽, 計(jì)算機(jī)國(guó)際競(jìng)賽 Date: 2019年5月17日下午6:12

The milk business is booming! Farmer John's milk processing factory consists of?N?processing stations, conveniently numbered?1…N?(1≤N≤100), and?N?1?walkways, each connecting some pair of stations. (Walkways are expensive, so Farmer John has elected to use the minimum number of walkways so that one can eventually reach any station starting from any other station).

To try and improve efficiency, Farmer John installs a conveyor belt in each of its walkways. Unfortunately, he realizes too late that each conveyor belt only moves one way, so now travel along each walkway is only possible in a single direction! Now, it is no longer the case that one can travel from any station to any other station.

However, Farmer John thinks that all may not be lost, so long?as?there is at least one station?i?such that one can eventually travel to station?i?from every other station. Note that traveling to station?i?from another arbitrary station?j?may involve traveling through intermediate stations between?i?and?j. Please help Farmer John figure out if such a station?i?exists.

INPUT FORMAT (file factory.in):

The first line contains an integer?N, the number of processing stations. Each of the next?N?1?lines contains two space-separated integers?ai?and?bi?with?1≤ai,bi≤N?and?ai≠bi. This indicates that there is a conveyor belt that moves from station?ai?to station?bi, allowing travel only in the direction from?ai?to?bi.

OUTPUT FORMAT (file factory.out):

If there exists a station?i?such that one can walk to station?i?from any other station, then output the minimal such?i. Otherwise, output??1.

SAMPLE INPUT:

3
1 2
3 2

SAMPLE OUTPUT:

Problem credits: Dhruv Rohatgi

中文版

牛奶生意正紅紅火火！Farmer John的牛奶加工廠內(nèi)有N個(gè)加工站，編號(hào)為1…N（1≤N≤100），以及N?1條通道，每條連接某兩個(gè)加工站。（通道建設(shè)很昂貴，所以Farmer John選擇使用了最小數(shù)量的通道，使得從每個(gè)加工站出發(fā)都可以到達(dá)所有其他加工站）。

為了創(chuàng)新和提升效率，F(xiàn)armer John在每條通道上安裝了傳送帶。不幸的是，當(dāng)他意識(shí)到傳送帶是單向的已經(jīng)太晚了，現(xiàn)在每條通道只能沿著一個(gè)方向通行了！所以現(xiàn)在的情況不再是從每個(gè)加工站出發(fā)都能夠到達(dá)其他加工站了。

然而，F(xiàn)armer John認(rèn)為事情可能還不算完全失敗，只要至少還存在一個(gè)加工站i滿足從其他每個(gè)加工站出發(fā)都可以到達(dá)加工站i。注意從其他任意一個(gè)加工站j前往加工站i可能會(huì)經(jīng)過(guò)i和j之間的一些中間站點(diǎn)。請(qǐng)幫助Farmer John求出是否存在這樣的加工站i。